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

Python으로 각 작업자에게 동전을 지급하는 방법의 수 계산하기

문제 개요

양수로 이루어진 두 개의 리스트 coins와 salaries가 있다고 가정해 보겠습니다. 여기서 coins[i]는 i번째 동전의 가치를 의미하고, salaries[j]는 j번째 작업자에게 지급해야 하는 최소 급여액을 나타냅니다.

각 종류의 동전은 하나씩만 존재하며, 모든 작업자에게 정확히 하나의 동전을 지급해야 합니다. 이때 동전을 지급할 수 있는 방법의 수를 구하는 것이 목표입니다. 두 가지 지급 방법 중 어떤 작업자가 받는 동전의 종류라도 서로 다르다면, 그 두 방법은 서로 다른 것으로 간주합니다. 만약 결과값이 매우 커진다면 10^9 + 7로 나눈 나머지를 반환하면 됩니다.

입력 예시 이해하기

예를 들어 coins = [1, 2, 3], salaries = [1, 2]라고 입력이 주어졌다고 합시다. 이때 출력은 4가 됩니다.

  • 가치가 1인 첫 번째 동전을 사용하지 않으면, 남은 두 동전(2와 3)은 두 작업자 모두에게 지급 가능하므로 지급 방법이 2가지 존재합니다.
  • 가치가 1인 동전을 사용하는 경우, 이 동전은 첫 번째 작업자(최소 급여 1)에게만 지급할 수 있고, 나머지 동전 중 아무거나 하나를 두 번째 작업자에게 줄 수 있습니다. 이 경우도 2가지입니다.

따라서 전체 지급 방법은 총 4가지가 됩니다.

해결 접근 방법

이 문제는 정렬과 이진 탐색(Binary Search)을 활용하여 효율적으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.

  1. coins 리스트와 salaries 리스트를 각각 오름차순으로 정렬합니다.
  2. num_coins := coins의 크기, num_salaries := salaries의 크기로 설정합니다.
  3. 결과를 저장할 빈 딕셔너리 dp를 생성합니다.
  4. 각 급여(salary)에 대해 이진 탐색을 수행하여 해당 급여 이상의 가치를 가진 첫 번째 동전의 인덱스(idx)를 찾습니다.
    • 탐색 범위를 l = 0, r = num_coins - 1로 초기화하고, idx는 기본적으로 num_coins로 설정합니다.
    • l <= r인 동안 중간 위치 m을 계산하며, coins[m] >= salary이면 idx를 m으로 갱신하고 탐색 범위를 왼쪽으로 좁힙니다. 그렇지 않으면 오른쪽으로 좁힙니다.
  5. 만약 idx가 num_coins와 같다면, 해당 급여를 지급할 수 있는 동전이 없다는 뜻이므로 즉시 0을 반환합니다.
  6. 찾은 인덱스를 dp[salary]에 저장합니다.
  7. 급여가 큰 작업자부터 역순으로 순회하면서, 각 작업자가 선택할 수 있는 동전의 개수를 곱하여 누적 결과(res)를 계산합니다.
  8. 최종적으로 res를 10^9 + 7로 나눈 나머지를 반환합니다.
💡 참고: 파이썬에서는 bisect_left 함수를 사용하면 위의 이진 탐색 로직을 직접 구현하지 않고도 동일한 인덱스를 손쉽게 구할 수 있습니다.

구현 코드

아래 예제를 통해 실제 구현을 확인해 보겠습니다.

class Solution:
    def solve(self, coins, salaries):
        coins.sort()
        salaries.sort()
        num_coins = len(coins)
        num_salaries = len(salaries)
        dp = {}
        for salary in salaries:
            l = 0
            r = num_coins - 1
            idx = num_coins
            while l <= r:
                m = l + (r - l) // 2
                if coins[m] >= salary:
                    idx = m
                    r = m - 1
                else:
                    l = m + 1
            if idx == num_coins:
                return 0
            dp[salary] = idx
        res = 1
        for i in range(num_salaries - 1, -1, -1):
            salary = salaries[i]
            idx = dp[salary]
            res *= (num_coins - idx + 1) - (num_salaries - i)
        return res % (10**9+7)

ob = Solution()
coins = [1, 2, 3]
salaries = [1, 2]
print(ob.solve(coins, salaries))

입력

[1, 2, 3],[1, 2]

출력

4

마무리

이 알고리즘은 정렬에 O(N log N), 각 급여에 대한 이진 탐색에 O(log M)의 시간이 소요되므로 전체 시간 복잡도는 O((N + M) log N) 수준으로 효율적입니다. 급여가 높은 작업자부터 처리하면 선택 가능한 동전의 범위가 자연스럽게 제한되므로, 경우의 수를 곱셈으로 누적하는 방식으로 정답을 구할 수 있습니다.