문제 개요
리마(Rima)에게 정수 배열 형태로 주어진 카드 패가 있다고 가정해 봅시다. 그녀는 이 카드들을 크기가 정확히 W인 그룹들로 나누려고 하며, 각 그룹은 반드시 연속된 값의 카드 W장으로 구성되어야 합니다. 우리가 할 일은 이러한 그룹화가 가능한지 여부를 판단하는 것입니다.
예를 들어 카드가 [1,2,3,6,2,3,4,7,8]이고 W = 3이라면, 카드를 [1,2,3], [2,3,4], [6,7,8]처럼 세 그룹으로 재배열할 수 있으므로 답은 true입니다.
접근 방법
이 문제는 맵(Map)과 그리디(Greedy) 기법을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 항상 가장 작은 값부터 그룹을 만들어 나가는 것입니다. C++의 map은 키가 자동으로 오름차순 정렬되므로, 가장 작은 카드부터 순서대로 처리하기에 적합합니다.
다음 단계에 따라 문제를 해결할 수 있습니다.
- 맵 m을 정의하고, 각 카드 값의 등장 빈도를 m에 저장합니다.
- 전체 카드 수(n)가 0이 될 때까지 다음 과정을 반복합니다.
- prev := 0 으로 초기화합니다.
- it := 맵의 첫 번째 키-값 쌍을 가리키는 반복자(iterator)로 설정합니다.
- i를 0부터 W-1까지 반복합니다.
- it가 가리키는 값(빈도)이 0이면, 다음 쌍을 가리키도록 이동합니다.
- i > 0이면서 (it의 키 − 1) == prev이거나, i == 0인 경우:
- it의 빈도를 1 감소시킵니다.
- prev := it의 키로 갱신합니다.
- 그렇지 않으면 연속성이 깨진 것이므로 false를 반환합니다.
- it를 다음 쌍으로 이동시킵니다.
- n := n − W 로 갱신하여 하나의 그룹을 완성했음을 반영합니다.
- 모든 그룹이 성공적으로 구성되면 true를 반환합니다.
또한 시작 전에 n % W != 0인 경우를 먼저 확인하면, 카드 수가 W로 나누어떨어지지 않을 때 즉시 false를 반환하여 불필요한 계산을 줄일 수 있습니다.
구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isNStraightHand(vector<int>& hand, int W) {
map <int, int> m;
int n = hand.size();
if(n % W != 0) return false;
for(int i = 0; i < n; i++){
m[hand[i]]++;
}
while(n){
map <int, int> :: iterator it = m.begin();
int prev = 0;
for(int i = 0; i < W; i++){
while(it->second == 0) it++;
if((i > 0 && it->first - 1 == prev) || i == 0){
it->second--;
prev = it->first;
}else{
return false;
}
it++;
}
n -= W;
}
return true;
}
};
main(){
vector<int> v = {1,2,3,6,2,3,4,7,8};
Solution ob;
cout << (ob.isNStraightHand(v, 3));
}입력
[1,2,3,6,2,3,4,7,8] 3
출력
1
코드 설명 및 복잡도 분석
먼저 모든 카드의 빈도를 맵에 기록한 뒤, 남은 카드가 없을 때까지 가장 작은 값부터 W개씩 이어지는 그룹을 만듭니다. 중간에 연속되지 않는 값이 발견되면 곧바로 false를 반환하므로, 잘못된 입력을 조기에 걸러낼 수 있습니다.
시간 복잡도: 맵 삽입에 O(n log n), 그룹화 과정에서 각 카드를 한 번씩 처리하므로 전체 O(n log n)입니다.
공간 복잡도: 서로 다른 카드 값의 개수에 비례하여 최대 O(n)의 추가 공간이 필요합니다.