C++에서 주어진 차이를 만족하는 가장 긴 등차 부분 수열 구하기

문제 개요

정수 배열 arr과 정수 difference가 주어졌을 때, 인접한 원소 간의 차이가 모두 difference와 같은 가장 긴 등차 부분 수열의 길이를 찾아야 합니다.

예를 들어 입력이 [1,5,7,8,5,3,4,2,1]이고 difference가 -2라면, 출력은 4입니다. 이 경우 가장 긴 등차 수열은 [7,5,3,1]이며, 인접한 원소들이 모두 -2씩 감소하기 때문입니다.

풀이 접근 방식

이 문제는 해시 맵을 활용한 동적 계획법(DP)으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

m[x] = 값 x로 끝나는 가장 긴 등차 부분 수열의 길이

현재 원소 x를 처리할 때, x - d로 끝나는 부분 수열이 이미 존재한다면 그 뒤에 x를 붙여 길이를 1 늘릴 수 있습니다. 따라서 점화식 m[x] = m[x - d] + 1이 성립합니다. 배열을 한 번만 순회하면서 각 값을 갱신하면 되므로, std::map을 사용하면 전체 O(n log n), unordered_map을 사용하면 평균 O(n)의 시간 복잡도로 해결됩니다.

알고리즘 단계

맵 m을 하나 선언합니다.
n := 배열 arr의 크기로 설정하고, ans := 0으로 초기화합니다.
i를 0부터 n - 1까지 반복합니다.
- x := arr[i]
- m[x] := 1 + m[x - d]
- ans := max(ans, m[x])
ans를 반환합니다.

C++ 구현 예제

다음 구현을 통해 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int longestSubsequence(vector<int>& arr, int d) {
      int n = arr.size();
      map <int,int> m;
      int ans = 0;
      for(int i =0;i<n;i++){
         int x = arr[i];
         m[x] = 1 + (m[x-d]);
         ans = max(ans,m[x]);
      }
      return ans;
   }
};
main(){
   vector<int> v1 = {1,5,7,8,5,3,4,2,1};
   Solution ob;
   cout <<ob.longestSubsequence(v1, -2);
}

동작 과정 살펴보기

입력 [1,5,7,8,5,3,4,2,1]과 d = -2일 때 맵 m의 변화를 추적하면 다음과 같습니다.

x = 1 → m[1] = m[3] + 1 = 1
x = 5 → m[5] = m[7] + 1 = 1
x = 7 → m[7] = m[9] + 1 = 1
x = 8 → m[8] = m[10] + 1 = 1
x = 5 → m[5] = m[7] + 1 = 2
x = 3 → m[3] = m[5] + 1 = 3
x = 4 → m[4] = m[6] + 1 = 1
x = 2 → m[2] = m[4] + 1 = 2
x = 1 → m[1] = m[3] + 1 = 4

최종적으로 ans는 4가 되며, 이는 등차 수열 [7,5,3,1]의 길이와 일치합니다.

입력

[1,5,7,8,5,3,4,2,1]
-2