문제 링크: https://leetcode.com/problems/maximum-alternating-subsequence-sum/
문제 설명
어떤 배열의 alternating sum (교차 합) 은 그 배열에서의 홀수 번째 원소는 더하고, 짝수 번째 원소는 뺀 값의 합을 의미한다. 예를 들어서, [4,2,5,3] 배열에 대한 교차 합은, (4+5)-(2+3)=4 가 된다.
이러한 배경지식에서, 특정 배열 nums 가 주어졌을 때, nums 배열에서 뽑을 수 있는 임의의 subsequence (부분열) 들의 교차 합 중 최대 값을 구하는 것이 문제이다.
부분열이라고 하면, 주어진 배열에서 일부 원소들을 제거는 하되, 원소들의 상대적인 순서는 유지한 새로운 배열을 말한다. 예를 들어서, [4,2,3,7,2,1,4] 배열에 대해서 [2,7,4] 는 부분열이라고 할 수 있지만, [2,4,2] 는 부분열이라고 할 수 없다.
예시 입출력
1
2
3
Input: nums = [4,2,5,3]
Output: 7
Explanation: It is optimal to choose the subsequence [4,2,5] with alternating sum (4 + 5) - 2 = 7.
1
2
3
Input: nums = [5,6,7,8]
Output: 8
Explanation: It is optimal to choose the subsequence [8] with alternating sum 8.
1
2
3
Input: nums = [6,2,1,2,4,5]
Output: 10
Explanation: It is optimal to choose the subsequence [6,1,5] with alternating sum (6 + 5) - 1 = 10.
주어지는 nums 배열에 대한 제한사항은 아래와 같다.
1
2
3
Constraints:
- 1 <= nums.length <= 105
- 1 <= nums[i] <= 105
나의 해답
우선 이 문제는 Bruteforce 하게 풀기에는 너무 많은 값을 체크해야 한다. nums.length 를 n 으로 잡으면, nums 배열의 부분열은 nC1, nC2, nC3, … nCn 만큼 경우의 수가 존재하기 때문에 이들에 대한 alternating sum 을 다 구해서 최대값을 구해야 한다. 당연히 이 것은 정답을 내뱉을 수는 있으나 시간 복잡도 상 매우 비효율적인 풀이가 된다.
좀 더 쉽게 풀 수 있는 방법이 있는데, 각 원소가 부분열의 홀수번째 원소로 올 경우의 정답과 짝수번째 원소로 올 경우의 정답을 기록해두고, 그 값을 이용해서 동적 계획법 (Dynamic Programming) 을 통해 풀이하는 것이다.
각 원소마다 두 개의 정답을 저장하여 memoization 기법을 사용한다. 각 원소가 부분열의 홀수번째 원소로 올 경우에 대한 정답, 짝수번째 원소로 올 경우에 대한 정답을 저장한다.
이렇게 하고 나면, 동적 계획법 풀이를 위한 점화식을 떠올려야 할텐데, 마지막 원소가 부분열의 홀수번째 원소로 오려면, 그 직전 원소는 짝수번째 원소로 와야 하며, 반대 경우도 마찬가지가 된다. 즉, 아래와 같은 점화식을 세울 수 있다. (슈도코드로 작성)
f(nums) = nums 의 마지막 원소 nums[n-1] 값이 부분열의 홀수번째 원소가 될 경우의 nums 부분열의 최대 교차합
p(nums) = nums 의 마지막 원소 nums[n-1] 값이 부분열의 짝수번째 원소가 될 경우의 nums 부분열의 최대 교차합
f(nums) = max(f(nums[0:n-1]), p(nums[0:n-1]) + nums[n-1])
p(nums) = max(p(nums[0:n-1]), f(nums[0:n-1]) - nums[n-1])
즉, 두 개의 점화식이 서로 크로스하면서 계속 memoization 을 활용하며 최종적으로 f(arr), p(arr) 을 구할 수 있고 이 둘 중의 최대값이 정답이 된다. 그런데, 최대값은 무조건 f(arr) 일 수 밖에 없는데, 모든 원소는 양수이기 때문에, 덧셈의 대상 (홀수번째 원소) 이 하나라도 더 많아야 값이 더 커지게 된다.
이것을 그대로 Typescript 코드로 옮기면 아래와 같다.
나의 해답 코드 1
1
2
3
4
5
6
7
8
9
10
11
function maxAlternatingSum(nums: number[]): number {
const memo = new Array(nums.length).fill({}).map(o => [0, 0]);
memo[0][0] = nums[0];
for (let i = 1; i < nums.length; i++) {
memo[i][0] = Math.max(memo[i - 1][0], memo[i - 1][1] + nums[i]);
memo[i][1] = Math.max(memo[i - 1][1], memo[i - 1][0] - nums[i]);
}
return memo[nums.length - 1][0];
};
memo 라는 변수는 n x 2 배열인데, memo[i][0] 의 경우 nums[i] 가 부분열의 홀수번째 원소일 경우의 정답, nums[i][1] 의 경우 nums[i] 가 부분열의 짝수번째 원소일 경우의 정답이다.
우선 첫번째 원소의 경우 무조건 홀수번째 원소가 될 수밖에 없다. 자기 자신만으로 이뤄진 부분열 밖에 만들수 없기 때문이다. 그래서 초기화는 memo[0][0] = nums[0] 으로 충분하다.
그리고 memo[i][0] 의 경우 기존의 memo[i-1][0] 을 그대로 계승하되 (해당 인덱스의 원소가 부분열로 포함 안되는 경우도 감안), 직전 원소가 짝수번째인 케이스는 반드시 마지막 원소인 nums[i] 가 부분열에 포함되야만 교차합이 커지게 된다. (모든 원소가 양수이므로 부분열은 반드시 홀수 갯수를 가져야만 교차합이 커지게 된다.) 이러한 이유로, memo[i][0] 은 memo[i-1][0] 혹은 memo[i-1][1] + nums[i] 중 큰 값이 정답이 된다. memo[i][1] 도 거의 비슷한 맥락으로 이해할 수 있다.
또한 위에서 언급한 것처럼, 모든 원소가 양수이기 때문에 가장 마지막 원소가 짝수번째 원소로 오는 케이스보다는 홀수번째 원소로 오는 케이스에서 교차합이 더 커지게 된다. (홀수번째 원소는 더하기를 하므로) 최종적으로는 memo[nums.length - 1][0] 이 정답이 된다. 굳이 Math.max(...memo[nums.length-1]) 을 할 필요가 없다는 것이다.
나의 해답 코드 2
위 방식대로 풀어도 충분히 문제는 효율적으로 잘 풀게 되었다. 그런데 좀 더 효율적으로 풀 수 있는 방법은 없을까 고민이 되었다. 일단, 점화식 자체가 바로 직전의 memoization 만을 활용하기 때문에 굳이 memo 라는 변수를 n x 2 만큼 다 가지고 있을 필요가 없다고 느꼈다. 즉, 공간 복잡도에서 좀 더 개선의 여지가 있다고 느꼈다.
공간 복잡도를 좀 더 개선한 새로운 코드를 아래와 같이 작성해보았다.
1
2
3
4
5
6
7
8
9
10
11
function maxAlternatingSum(nums: number[]): number {
let resultOdd = 0;
let resultEven = 0;
for (let i = 0; i < nums.length; i++) {
resultOdd = Math.max(resultOdd, resultEven + nums[i]);
resultEven = Math.max(resultEven, resultOdd - nums[i]);
}
return resultOdd;
};
resultOdd, resultEven 은 위에서 언급한 memo[i][0], memo[i][1] 과 같은 개념이다. 특정 인덱스까지의 배열에 대한 부분열의 교차합을 구할 때, 해당 인덱스의 원소가 홀수번째가 될 경우와 짝수번째가 될 경우에 대한 최대 교차합을 의미한다.
resultOdd 는 기존의 resultOdd 를 계승하되, 이전 resultEven 값에 현재 인덱스의 원소값을 더한 값과 비교하여 최대값을 채택하게 된다. 의미상으로는 위 코드와 완전히 동일하다. 유일한 차이는 memo 라는 변수를 n x 2 배열로 만들었느냐, 아니면 계속 반복되는 memoization 표현을 변수 2개만으로 풀어나갔냐의 차이 뿐이다.
GitHub 에서의 위 소스 코드 위치: https://github.com/jeongmincha/solving-algorithm/blob/master/leetcode/medium/1911-maximum-alternating-subsequence-sum.ts