숫자로 이루어진 리스트 nums와 하나의 정수 k가 주어졌을 때, 이 리스트를 각각 정확히 k개의 값으로 구성되고 그 값들이 연속적으로 1씩 증가하는 여러 개의 부분 리스트로 나눌 수 있는지 확인해야 합니다.
예를 들어 입력이 nums = [4, 3, 2, 4, 5, 6], k = 3이라면 출력은 True가 됩니다. 리스트를 [2, 3, 4]와 [4, 5, 6] 두 그룹으로 분할할 수 있기 때문입니다. 각 그룹은 3개의 값을 가지며, 값들이 연속적으로 증가합니다.
문제 해결 접근 방법
이 문제는 맵(map)을 활용한 그리디(greedy) 방식으로 해결할 수 있습니다. 핵심 아이디어는 항상 가장 작은 시작값부터 연속된 k개의 수열을 찾아 제거해 나가는 것입니다. 알고리즘 단계는 다음과 같습니다.
- 각 숫자의 등장 횟수를 저장하기 위한 맵을 하나 정의합니다.
- 리스트의 모든 원소에 대해 해당 숫자의 빈도를 맵에 1씩 증가시킵니다.
- 플래그 변수
ok를 true로 초기화합니다. - 맵이 비어 있지 않고
ok가 true인 동안 다음을 반복합니다.ok를 false로 설정합니다.- 맵의 각 키-값 쌍을 순회하면서, 현재 키에서 1을 뺀 값(즉, 바로 앞의 연속 숫자)이 맵에 없는지 확인합니다. 없다면 그 키는 새로운 수열의 시작점이 됩니다.
- 시작점부터
it.key부터it.key + k - 1까지의 모든 숫자가 맵에 존재하는지 검사합니다. 하나라도 없으면 플래그를 false로 만듭니다. - 모든 숫자가 존재한다면(flag가 true라면), 해당 범위의 숫자들을 맵에서 하나씩 제거하고, 빈도가 0이 된 키는 맵에서 삭제합니다. 그런 다음
ok를 true로 설정하고 내부 루프를 탈출합니다.
- 마지막에 맵이 비어 있다면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
이 방식이 동작하는 이유는, 어떤 숫자 x의 직전 값(x-1)이 더 이상 남아 있지 않다면 x는 반드시 새로운 수열의 첫 번째 원소여야 하기 때문입니다. 따라서 x부터 시작하는 연속 k개의 수열을 만들 수 없다면 전체 분할은 불가능합니다.
아래 예제 코드를 통해 더 자세히 이해해 보겠습니다.
예제 코드
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
bool solve(vector<int> nums, int k) {
map <int, int> m;
for(auto& it : nums){
m[it]++;
}
bool ok = true;
while(m.size() && ok){
ok = false;
for(auto& it : m){
if(!m.count(it.first - 1)){
bool flag = true;
for(int i = it.first; i <= it.first + k - 1;i++){
if(!m.count(i))
flag = false;
}
if(flag){
for(int i = it.first; i <= it.first + k - 1;i++){
m[i]--;
if(m[i] == 0)
m.erase(i);
}
ok = true;
break;
}
}
}
return m.empty();
}
};
main(){
vector<int> v = {4, 3, 2, 4, 5, 6};
Solution ob;
cout << ob.solve(v, 3);
}
입력
{4, 3, 2, 4, 5, 6}출력
1
출력값 1(true)은 주어진 리스트가 조건에 맞게 분할될 수 있음을 의미합니다. 이 알고리즘의 시간 복잡도는 대략 O(n²)이며, n은 리스트의 길이입니다. 각 반복마다 최소 k개의 원소가 맵에서 제거되기 때문에 실제로는 입력 크기에 비례하여 유한한 횟수 안에 종료됩니다.