Python – 정수 리스트를 조건에 맞는 그룹으로 나눌 수 있는지 확인하기

문제 설명

숫자로 이루어진 리스트 nums가 주어졌을 때, 이 리스트를 하나 이상의 그룹으로 나눌 수 있는지 확인해야 합니다. 단, 나눈 그룹은 다음 세 가지 조건을 모두 만족해야 합니다.

각 그룹의 크기는 2 이상이어야 합니다.
모든 그룹의 크기는 서로 같아야 합니다.
같은 그룹 안에 들어 있는 숫자는 모두 동일해야 합니다.

예를 들어 입력이 [3, 4, 6, 9, 4, 3, 6, 9]라면 결과는 True입니다. 각 숫자(3, 4, 6, 9)가 정확히 두 번씩 등장하므로, 같은 숫자끼리 두 개씩 묶어 총 네 개의 그룹을 만들 수 있기 때문입니다.

접근 방법

이 문제의 핵심은 각 숫자의 등장 횟수(빈도)에 주목하는 것입니다. 모든 빈도의 최대공약수(GCD)를 g라고 하면, 각 그룹의 크기를 g로 하여 전체 리스트를 균등하게 나눌 수 있습니다. 반대로 최대공약수가 1이라면 그룹 크기를 2 이상으로 맞출 방법이 없으므로 나누는 것이 불가능합니다.

따라서 해결 절차는 다음과 같습니다.

Counter를 사용해 각 고유 숫자와 그 빈도를 담은 맵을 만듭니다.
임시 변수 temp를 0으로 초기화합니다.
각 빈도를 순회하면서 다음을 수행합니다.
- temp가 0이면(첫 번째 빈도) 해당 값을 temp에 저장합니다.
- 그렇지 않으면 현재 빈도와 temp의 최대공약수를 구해 temp에 저장합니다.
- temp가 1이 되는 순간 더 이상 조건을 만족할 수 없으므로 False를 반환합니다.
모든 빈도를 통과했다면 True를 반환합니다.

구현 예제

from collections import Counter
import math

class Solution:
    def solve(self, nums):
        counts = Counter(nums)
        temp = 0
        for count in counts:
            if temp == 0:
                temp = counts[count]
            else:
                temp = math.gcd(counts[count], temp)
                if temp == 1:
                    return False
        return True

ob = Solution()
L = [3, 4, 6, 9, 4, 3, 6, 9]
print(ob.solve(L))

입력

[3, 4, 6, 9, 4, 3, 6, 9]

출력

True

동작 원리 살펴보기

위 입력에서 각 숫자의 빈도는 다음과 같습니다.

3 → 2회
4 → 2회
6 → 2회
9 → 2회

모든 빈도의 최대공약수는 2이며, 1이 아니므로 각 그룹의 크기를 2로 하여 성공적으로 분할할 수 있습니다. 만약 입력이 [1, 2, 3, 1, 2]였다면 빈도는 각각 2, 2, 1이고 최대공약수가 1이 되어 False가 반환됩니다.

더 간결한 대안 코드

Python의 functools.reduce를 활용하면 같은 로직을 한 줄로 표현할 수 있습니다. 이 버전은 첫 번째 빈도가 1인 경우(예: [5])까지 올바르게 처리한다는 장점이 있습니다.

from collections import Counter
from functools import reduce
from math import gcd

class Solution:
    def solve(self, nums):
        return reduce(gcd, Counter(nums).values()) >= 2

두 코드 모두 시간 복잡도는 O(n)이며, 공간 복잡도는 고유 숫자의 개수에 비례합니다.