정수가 적혀 있는 카드 한 벌(deck)이 있다고 가정해 보겠습니다. 확인해야 할 것은 X ≥ 2인 값을 선택했을 때, 전체 덱을 하나 이상의 그룹으로 나눌 수 있는지 여부입니다. 이때 각 그룹은 다음 조건을 만족해야 합니다.
- 각 그룹은 정확히 X장의 카드로 구성되어야 합니다.
- 같은 그룹에 속한 모든 카드에는 동일한 숫자가 적혀 있어야 합니다.
예를 들어 입력이 deck = [1,2,3,4,4,3,2,1]이라면 출력은 true가 됩니다. [1,1], [2,2], [3,3], [4,4]처럼 같은 숫자끼리 두 장씩 묶어 나눌 수 있기 때문입니다.
해결 접근 방법
이 문제의 핵심은 각 숫자의 등장 횟수를 구한 뒤, 모든 횟수의 최대공약수(GCD)를 계산하는 것입니다. 모든 개수가 1보다 큰 공통 약수를 가진다면, 그 약수를 X로 삼아 덱을 원하는 형태로 나눌 수 있습니다. 문제 풀이 단계는 다음과 같습니다.
- 맵(map) 정의: 숫자별 등장 횟수를 저장할 맵 mp를 선언합니다.
- 빈도 계산: 덱의 모든 카드 x에 대해 mp[x]의 값을 1씩 증가시킵니다.
- GCD 계산: mp의 모든 키-값 쌍에 대해 ans와 해당 값(value)의 최대공약수를 구해 ans에 저장합니다.
- 결과 반환: ans가 1보다 크면 true를, 그렇지 않으면 false를 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool hasGroupsSizeX(vector<int>& deck) {
unordered_map<int, int> mp; // 숫자별 등장 횟수를 저장할 맵
int ans = 0;
for (auto x : deck)
mp[x]++; // 각 카드 숫자의 빈도 증가
for (auto x : mp)
ans = __gcd(ans, x.second); // 모든 빈도의 최대공약수 계산
return (ans > 1); // 공약수가 1보다 크면 true 반환
}
};
main(){
Solution ob;
vector<int> v = {1,2,3,4,4,3,2,1};
cout << (ob.hasGroupsSizeX(v));
}입력
{1,2,3,4,4,3,2,1}출력
1
동작 원리 살펴보기
위 예제에서 각 숫자의 등장 횟수는 1이 2회, 2가 2회, 3이 2회, 4가 2회입니다. 네 값의 최대공약수는 2이므로 X = 2를 선택할 수 있고, 프로그램은 true(1)를 반환합니다. 반면 어떤 숫자가 단 한 번만 등장한다면 최대공약수는 1이 되어, 조건을 만족하는 그룹으로 나누는 것이 불가능해집니다.
참고로 원래 코드에서는 변수 ans가 초기화되지 않은 상태로 사용되었는데, 이는 정의되지 않은 동작(undefined behavior)을 유발할 수 있으므로 위 예제에서는 ans = 0으로 초기화했습니다. __gcd(0, n)은 n을 그대로 반환하므로 로직에는 전혀 영향을 주지 않으면서 안전성만 확보할 수 있습니다.