한 신발 가게에 서로 다른 사이즈의 신발 n개가 배열 size에 담겨 있고, m명의 고객에 대한 수요 목록 demand가 주어진다고 가정해 봅시다. demand[i]는 (신발_사이즈, 지불_금액) 형태의 튜플로, i번째 고객은 해당 사이즈의 신발을 원하며 명시된 금액을 지불할 의사가 있습니다. 이때 우리가 구해야 할 것은 가게 주인이 신발을 판매하여 벌 수 있는 총 금액입니다.
문제 예시
입력이 다음과 같다고 해보겠습니다.
shoes = [2,3,4,5,6,8,7,6,5,18]
demand = [(6,55), (6,45), (6,55), (4,40), (18,60), (10,50)]
이 경우 출력은 200이 됩니다. 그 과정은 다음과 같습니다.
첫 번째 고객은 사이즈 6의 신발을 55에 구매합니다.
두 번째 고객은 사이즈 6의 신발을 45에 구매합니다.
세 번째 고객은 사이즈 6의 신발이 더 이상 재고에 없어 구매하지 못합니다.
네 번째 고객은 사이즈 4의 신발을 40에 구매합니다.
다섯 번째 고객은 사이즈 18의 신발을 60에 구매합니다.
여섯 번째 고객은 사이즈 10의 신발이 없어 구매하지 못합니다.
따라서 총 수익은 55 + 45 + 40 + 60 = 200입니다.
해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- n := 수요(demand) 목록의 길이
- sizes := 신발 사이즈별 빈도수를 저장하는 맵(Counter)
- earn := 0으로 초기화
- i를 0부터 n-1까지 반복:
- (sz, price) := demand[i]
- 사이즈 sz의 신발이 sizes에 존재하면:
- sizes[sz] := sizes[sz] - 1 (재고 1개 차감)
- earn := earn + price (수익 누적)
- earn 반환
구현 예시
다음 구현을 통해 더 자세히 이해해 보겠습니다.
from collections import Counter
def solve(shoes, demand):
n = len(demand)
sizes = Counter(shoes)
earn = 0
for i in range(n):
sz, price = demand[i]
if sizes[sz]:
sizes[sz] -= 1
earn += price
return earn
shoes = [2,3,4,5,6,8,7,6,5,18]
demand = [(6,55), (6,45), (6,55), (4,40), (18,60), (10,50)]
print(solve(shoes, demand))
코드 설명
collections 모듈의 Counter 클래스를 사용하면 신발 사이즈별 재고 개수를 손쉽게 집계할 수 있습니다. 이후 각 고객의 요청을 순서대로 확인하면서 해당 사이즈의 재고가 남아 있는지 검사하고, 재고가 있다면 하나를 차감한 뒤 지불 금액을 수익에 더합니다. 만약 해당 사이즈의 재고가 소진되었다면 그 고객은 구매하지 못하고 넘어갑니다. 이 알고리즘의 시간 복잡도는 O(n)이며, 공간 복잡도 역시 O(n)으로 매우 효율적입니다.
입력
[2,3,4,5,6,8,7,6,5,18], [(6,55), (6,45), (6,55), (4,40), (18,60),
(10,50)]
출력
200