Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬으로 반복되는 정수를 분배하는 프로그램 – 백트래킹 풀이

문제 개요

정수 배열 nums가 주어지며, 서로 다른 값은 최대 50개까지만 존재한다고 가정합니다. 또 하나의 배열 quantity가 있고, quantity[i]는 i번째 고객이 주문한 아이템의 개수를 의미합니다. 우리는 nums의 값을 다음 조건을 모두 만족하도록 분배할 수 있는지 확인해야 합니다.

  • i번째 고객은 정확히 quantity[i]개의 아이템을 받아야 합니다.
  • i번째 고객이 받는 아이템들의 값은 모두 같아야 합니다.
  • 모든 고객이 만족해야 합니다.

예를 들어 입력이 nums = [5,1,2,2,3,4,4,3,3], quantity = [2,2,3]이라면 결과는 True입니다. 앞의 두 고객은 각각 두 개씩 원하므로 [2,2]와 [4,4]를 나눠주고, 세 번째 고객은 세 개를 원하므로 [3,3,3]을 주면 되기 때문입니다.

풀이 접근 방식

이 문제는 백트래킹(backtracking)으로 해결할 수 있습니다. 핵심 아이디어는 값 자체가 아니라 "빈도의 빈도(frequency of frequencies)"를 관리하는 것입니다. 즉, 각 값이 몇 번 등장했는지를 먼저 세고, 그 빈도들이 각각 몇 개 존재하는지를 카운터에 저장합니다. 이후 요구 수량이 많은 고객부터 순서대로 배정하고, 배정 후 남은 개수를 다시 카운터에 기록하면서 모든 경우를 탐색합니다.

구체적인 단계는 다음과 같습니다.

  1. util(i, cntr) 함수를 정의합니다.
  2. i가 quantity의 길이와 같다면 모든 고객에게 배정이 완료된 것이므로 True를 반환합니다.
  3. temp_counter에 cntr의 복사본을 저장합니다.
  4. cntr의 각 빈도 cnt에 대해 다음을 수행합니다.
    • cnt >= quantity[i]인 경우, 해당 빈도의 개수를 하나 차감하고 0이 되면 삭제합니다.
    • rem = cnt - quantity[i]를 계산하여 남은 개수를 temp_counter[rem]에 더합니다.
    • util(i+1, temp_counter)가 참이면 True를 반환합니다.
    • 실패했다면 변경 사항을 모두 되돌려 원래 상태로 복원합니다(백트래킹).
  5. 모든 시도가 실패하면 False를 반환합니다.
  6. 메인 로직에서는 Counter(nums)로 값별 빈도를 구한 뒤, 그 빈도들의 빈도로 최종 카운터를 만듭니다.
  7. quantity를 내림차순으로 정렬합니다. 요구량이 큰 고객을 먼저 처리하면 선택지가 줄어들어 가지치기 효과가 커집니다.
  8. util(0, cnt)의 결과를 반환합니다.

구현 예제

아래 파이썬 코드를 보면 이해가 더 쉽습니다.

from collections import Counter

def solve(nums, quantity):
    def util(i, cntr):
        if i == len(quantity):
            return True

        temp_counter = cntr.copy()
        for cnt in cntr:
            if cnt >= quantity[i]:
                temp_counter[cnt] -= 1
                if temp_counter[cnt] == 0:
                    temp_counter.pop(cnt)

                rem = cnt - quantity[i]
                temp_counter[rem] += 1

                if util(i + 1, temp_counter):
                    return True

                # 백트래킹: 상태 복원
                temp_counter[rem] -= 1
                if temp_counter[rem] == 0:
                    temp_counter.pop(rem)
                temp_counter[cnt] += 1

        return False

    cnt = Counter(Counter(nums).values())
    quantity.sort(reverse=True)
    return util(0, cnt)

nums = [5, 1, 2, 2, 3, 4, 4, 3, 3]
quantity = [2, 2, 3]
print(solve(nums, quantity))

입력

[5,1,2,2,3,4,4,3,3], [2,2,3]

출력

True

마무리

이 풀이는 이론적으로 지수 시간이 걸릴 수 있지만, 서로 다른 값이 최대 50개로 제한되고 요구 수량을 내림차순으로 처리해 가지치기를 하기 때문에 실제 환경에서 충분히 빠르게 동작합니다. "빈도의 빈도"만 추적하면 실제 값이 무엇인지는 중요하지 않다는 점이 이 문제의 핵심 포인트입니다.