정수 배열 nums와 양의 정수 k가 주어졌을 때, 이 배열을 각각 k개의 연속된 숫자로 이루어진 집합들로 나눌 수 있는지 판별하는 문제입니다. 나누는 것이 가능하면 true를, 불가능하면 false를 반환해야 합니다.
예를 들어 입력이 [1,2,3,3,4,4,5,6]이고 k = 4라면, 출력은 true가 됩니다. 배열을 [1,2,3,4]와 [3,4,5,6] 두 그룹으로 나눌 수 있기 때문입니다.
문제 해결 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- 숫자의 등장 횟수를 저장할 맵(map) m을 생성하고, n := nums 배열의 크기로 설정합니다.
- nums의 각 원소 e에 대해 m[e] 값을 1씩 증가시킵니다.
- cnt := 0으로 초기화합니다.
- nums 배열을 오름차순으로 정렬합니다.
- i를 0부터 n까지 반복하면서 다음을 수행합니다.
- x := nums[i]로 설정합니다.
- m[x - 1] == 0이고 m[x] > 0인 경우(즉, x가 새로운 그룹의 시작점인 경우):
- l := k로 저장합니다.
- k > 0인 동안 반복하며, m[x] > 0이면 m[x]를 1 감소시키고, 그렇지 않으면 false를 반환합니다.
- x와 cnt를 1씩 증가시키고, k를 1씩 감소시킵니다.
- 반복이 끝나면 k := l로 복원합니다.
- cnt == n이면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
핵심 아이디어는 정렬된 배열에서 각 숫자가 이전 숫자(x-1)보다 먼저 소모되어야 한다는 점입니다. x - 1이 맵에 존재하지 않는다면 x는 어떤 연속 시퀀스의 시작점이 되므로, 해당 지점부터 k개의 연속된 숫자를 하나씩 소모하며 그룹을 만듭니다. 모든 원소가 정확히 하나의 그룹에 속했다면 cnt가 n과 일치하게 됩니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isPossibleDivide(vector<int>& nums, int k) {
map <int, int> m;
int n = nums.size();
for(int i = 0; i < n; i++){
m[nums[i]]++;
}
int cnt = 0;
sort(nums.begin(), nums.end());
for(int i = 0; i < n; i++){
int x = nums[i];
if(m[x - 1] == 0 && m[x] > 0){
int l = k;
while(k>0){
if(m[x] > 0){
m[x]--;
} else return false;
x++;
k--;
cnt++;
}
k = l;
}
}
return cnt == n;
}
};
main(){
vector<int> v = {1,2,3,3,4,4,5,6};
Solution ob;
cout << (ob.isPossibleDivide(v, 4));
}입력
[1,2,3,3,4,4,5,6] 4
출력
1
출력값 1은 true를 의미하며, 주어진 배열이 k개의 연속된 숫자 집합으로 성공적으로 나누어질 수 있음을 보여줍니다. 이 알고리즘은 정렬에 O(n log n), 전체 처리에 O(n log n)의 시간 복잡도를 가지므로 효율적으로 동작합니다.