문제 개요
오름차순으로 정렬된 배열 nums가 주어졌을 때, 이 배열을 하나 이상의 부분 수열로 분할할 수 있는 경우에만 true를 반환하는 문제입니다. 단, 각 부분 수열은 다음 두 가지 조건을 반드시 만족해야 합니다.
- 수열을 구성하는 값들이 서로 연속된 정수여야 합니다. (예: 3, 4, 5)
- 각 부분 수열의 길이는 최소 3 이상이어야 합니다.
예를 들어 입력이 [1,2,3,3,4,4,5,5]라면 출력은 true입니다. 이 배열을 [1,2,3,4,5]와 [3,4,5]라는 두 개의 연속 시퀀스로 나눌 수 있기 때문입니다.
알고리즘 접근 방법
이 문제는 해시맵 기반 빈도 계산과 그리디(Greedy) 기법을 조합하면 효율적으로 해결할 수 있습니다. 해결 과정은 다음과 같습니다.
- 맵
m을 생성하여nums에 등장하는 각 숫자의 빈도를 저장하고, 배열의 크기를n에 저장합니다. cnt := n으로 초기화합니다. 여기서cnt는 아직 어느 부분 수열에도 배정되지 않은 원소의 개수를 의미합니다.- i를 0부터 n − 1까지 반복합니다.
x := nums[i]m[x],m[x + 1],m[x + 2]가 모두 존재하면, 즉 길이 3짜리 새로운 시퀀스를 시작할 수 있다면:m[x],m[x + 1],m[x + 2]를 각각 1씩 감소시키고,x에 3을 더한 뒤,cnt에서 3을 뺍니다.m[x] > 0이면서 동시에m[x] > m[x − 1]인 동안 다음을 반복합니다.cnt를 1 감소시키고,m[x]를 1 감소시키고,x를 1 증가시킵니다.
- 모든 반복이 끝난 후
cnt가 0이면 true를, 그렇지 않으면 false를 반환합니다.
배열이 오름차순으로 정렬되어 있으므로 값이 작은 원소부터 차례대로 처리됩니다. 여기서 m[x] > m[x − 1] 조건이 핵심인데, 현재 값 x의 남은 개수가 바로 앞 값(x − 1)보다 많다면 그 초과분은 기존 시퀀스에 붙일 수 없으므로 새로 만든 시퀀스를 계속 확장해야 한다는 직관을 반영합니다.
C++ 구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isPossible(vector<int>& nums) {
unordered_map <int, int> m;
int n = nums.size();
for(int i = 0; i < n; i++){
m[nums[i]]++;
}
int cnt = n;
for(int i = 0; i < n; i++){
int x = nums[i];
if(m[x] && m[x + 1] && m[x + 2]){
m[x]--;
m[x + 1]--;
m[x + 2]--;
x += 3;
cnt -= 3;
while(m[x] > 0 && m[x] > m[x - 1]){
cnt--;
m[x]--;
x++;
}
}
}
return cnt == 0;
}
};
main(){
vector<int> v = {1,2,3,3,4,4,5,5};
Solution ob;
cout << (ob.isPossible(v));
}
입력
[1,2,3,3,4,4,5,5]
출력
1
출력값 1은 bool 타입의 true에 해당하며, 주어진 배열이 조건을 만족하는 연속 부분 수열들로 성공적으로 분할되었음을 의미합니다. 해시맵 연산이 평균적으로 O(1)이므로 이 알고리즘의 시간 복잡도는 O(n)이며, 빈도 저장을 위한 해시맵 사용으로 공간 복잡도 역시 O(n)입니다.