[LeetCode # 446] Arithmetic Slices II - Subsequence

주어진 문제는 위와 같다. 정수형 배열이 주어졌을 때, 배열의 부분 배열 중 Arithmetic Subsequence 를 만족하는 부분 배열의 개수를 찾는 것.

 

Arithmetic Subsequence 란, 배열 내 인접한 원소들이 모두 동일한 차이값을 갖는 것을 의미하는데 원소가 3개 이상일 때만 이 조건을 만족한다. 예를 들어 [1, 2, 3, 4, 5] 는 인접한 원소의 차가 1 로 모두 동일하므로 조건을 만족하지만 [1, 2, 2, 3, 4] 는 인접한 원소의 차가 동일하지 않아 조건을 만족하지 않는다.

 

문제의 해결을 위해 DP 알고리즘을 적용했는데 그 방법은 다음과 같다. 배열의 각 인덱스를 탐색하며 현 위치를 기준으로 이전 위치까지 일정한 차를 갖는 Arithmetic Subsequence 가 존재했는 지 확인한 뒤 존재한다면 그 값을 현재 위치에 저장한다. 그리고 만약 이전 위치에 저장된 값이 있는 경우 그 값을 저장한 뒤 추후 반환한다.

 

예를 들어 설명하자면, [1, 1, 2, 3, 4, 5] 라는 배열이 존재할 때 찾고자 하는 Arithmetic Subsequence 는 [1, 2, 3] (2개), [1, 2, 3, 4] (2개), [1, 2, 3, 4, 5] (2개), [2, 3, 4, 5], [3, 4, 5], [1, 3, 5] (2개) 로 모두 11 개가 존재한다.

 

index	0	1	2	3	4	5
value	1	1	2	3	4	5

위와 같이 각 인덱스의 값이 존재하게 되는데, 현재 인덱스를 i, 이전 인덱스를 j 라고 표현한다.

 

1) i = 1, j = 0
현재 인덱스보다 이전 인덱스가 항상 존재해야 로직이 동작하므로 i = 0 일 경우는 스킵한다. value[i] 와 value[j] 는 모두 1로 동일하므로 값의 차이가 0이다. 따라서 i 위치에서 0의 차이를 갖는 Subsequence 가 한 개 존재함을 저장한다. 두 개의 원소만 가지고 판단한 것이므로 i 위치에 저장된 값은 정답에 반영하지 않는다.

 

2) i = 2, j = 0

value[i] 는 2, value[j] 는 1이므로 원소의 차가 1이다. 따라서 i 위치에서 1의 차를 갖는 Subsequence 가 한 개 존재함을 저장한다.

 

3) i = 2, j = 1

2) 와 마찬가지로 i 위치에 Subsequence 가 한 개 존재함을 저장한다. 2), 3) 의 정보는 각각 개별 정보이므로 i 위치에 1의 차를 갖는 Subsequence 는 두 개 존재하는 것으로 저장된다.

 

4) i = 3, j = 2

j 가 0, 1 일 때는 생략을 했는데 i 가 3일 때 해당 정보는 정답에 반영되지 않기 때문이다. value[i] 와 value[j] 의 차는 1이고, j 위치에 저장된 subsequence 의 개수는 2개이다. 즉, i 에서 차가 1인 subsequence 의 개수는 2개가 발생한다. i 가 3이 되었을 때, subsequence 의 길이가 비로소 3 이상이 되므로 이를 정답에 반영한다.

---

이와 같이 현재 위치를 탐색하며 이전 위치들에서 발생한 subsequence 의 개수를 더해 나간다. 현재 위치에서 발생한 개수는 정답에 반영하지 않고 이전 위치에 값이 존재할 경우에만 정답에 반영하는데, 위에 간략히 언급한 것처럼 원소 두 개를 기준으로 탐색하고 있고, 현재 위치에서 발생한 subsequence 는 원소 두 개만을 기준으로 작성한 것이기 때문이다.

 

현재 위치에서 저장하고 다음 위치에서 현재 위치를 확인했을 때 subsequence 가 존재한다면 원소를 3개 이상 조회한 결과이므로 비로소 정답에 반영할 수 있게 된다.

 

위와 같은 풀이로 작성한 소스 코드는 다음과 같다. 

 

class Solution {
public:
    int numberOfArithmeticSlices(vector<int> &nums) {
        if (nums.size() < 3) {
            return 0;
        }
        int ans = 0;
        vector<map<int, int>> dp(nums.size()); // [index, [diff, count]]

        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                long delta = (long) nums[i] - nums[j];
                if (delta >= INT_MAX || delta <= INT_MIN) {
                    continue;
                }
                int diff = nums[i] - nums[j];
                dp[i][diff] = dp[i][diff] + 1;
                if (dp[j].find(diff) != dp[j].end()) {
                    dp[i][diff] += dp[j][diff];
                    ans += dp[j][diff];
                }
            }
        }
        return ans;
    }
};

위의 설명과 코드를 연결해 설명하자면, dp 라고 선언한 map 의 배열이 위에서 subsequence 의 개수를 저장하기 위한 수단이다. 배열을 인덱스 개수만큼 생성을 해서 각 인덱스마다 따로 subsequence 를 저장하도록 했고, subsequence 는 단순하게 [공통의 차가 얼마인지, 해당 위치에 저장된 subsequence 의 개수가 몇 개인지] 를 표현하도록 했다.