정수 배열이 주어졌을 때, 가능한 모든 부분 수열(subsequence) 중에서 가장 긴 조화 부분 수열(harmonious subsequence)의 길이를 구하는 문제입니다.
여기서 조화 부분 수열이란 배열 안에 있는 값들 중 최댓값과 최솟값의 차이가 정확히 1인 수열을 의미합니다.
예를 들어 입력이 [1,3,2,2,5,2,3,7]이라면 출력은 5가 됩니다. 이는 가장 긴 조화 부분 수열이 [3,2,2,2,3]이며, 그 길이가 5이기 때문입니다.
문제 해결 접근 방법
이 문제는 해시 기반 맵(hash map)을 활용해 각 숫자의 등장 횟수를 세고, 인접한 두 숫자(k와 k+1)의 빈도수를 더하는 방식으로 효율적으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.
- 하나의 맵(map) m을 정의합니다.
- nums 배열의 각 원소 n에 대해 m[n]의 값을 1씩 증가시켜 빈도수를 기록합니다.
- 맵 m의 모든 키-값 쌍 (k, v)에 대해 다음을 수행합니다.
- it := 맵에서 (k + 1)을 탐색한 결과 위치
- 만약 it가 맵에 존재한다면, max_를 v와 해당 키의 빈도수를 합한 값 중 더 큰 값으로 갱신합니다.
- 모든 탐색이 끝나면 max_를 반환합니다.
이 접근법의 시간 복잡도는 O(n)이며, 공간 복잡도 역시 O(n)으로 매우 효율적입니다.
구현 예제
아래 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findLHS(vector<int>& nums) {
unordered_map<int, int> m;
for (const int n : nums)
++m[n];
int max_{ 0 };
for (const auto & [ k, v ] : m) {
auto it = m.find(k + 1);
if (it != m.end())
max_ = max(max_, v + it->second);
}
return max_;
}
};
main(){
Solution ob;
vector<int> v = {2,4,3,3,6,3,4,8};
cout << (ob.findLHS(v));
}입력
{2,4,3,3,6,3,4,8}출력
5
위 예제에서 숫자 3은 3번, 숫자 4는 2번 등장하므로 두 값을 합친 5가 정답이 됩니다. 숫자 2(1개)와 3(3개)의 조합은 4이므로 최대값이 아닙니다. 이처럼 각 숫자의 빈도를 맵에 저장한 뒤, 차이가 1인 인접 숫자 쌍의 빈도 합 중 최대값을 찾으면 문제를 간단히 해결할 수 있습니다.