대기열에 서 있는 고객들이 가지고 있는 지폐를 나타내는 배열 notes가 있다고 가정해 보겠습니다. 모든 고객은 50루피(Rs 50)짜리 티켓을 구매하려고 기다리고 있으며, 사용 가능한 지폐는 [50, 100, 200] 세 종류입니다. 이때 처음에 손에 든 돈이 0루피인 상태에서, 대기열 순서대로 모든 고객에게 티켓을 판매하고 거스름돈을 정확히 줄 수 있는지 확인해야 합니다.
예를 들어 입력이 notes = [50, 50, 100, 100]이라면 결과는 True입니다. 앞의 두 고객은 50루피 지폐를 그대로 받으면 되므로 거스름돈이 필요 없고, 이 시점에 우리 손에는 50루피 지폐 두 장이 있습니다. 따라서 뒤의 두 고객(각각 100루피 지폐 제시)에게는 50루피 지폐를 한 장씩 거스름돈으로 돌려주면 순서대로 모든 티켓을 판매할 수 있습니다.
해결 접근 방식
이 문제는 그리디(Greedy) 방식으로 해결할 수 있습니다. 각 지폐 액면가별 개수를 추적하면서, 고객이 지불한 금액에 따라 거스름돈을 전략적으로 반환하는 것입니다. 핵심 원칙은 다음과 같습니다.
- 50루피를 받은 경우: 거스름돈이 필요 없으므로 50루피 지폐 보유 개수를 1 증가시킵니다.
- 100루피를 받은 경우: 50루피 지폐 한 장을 거스름돈으로 줍니다. 만약 50루피 지폐가 없다면 판매를 계속할 수 없습니다.
- 200루피를 받은 경우: 우선 100루피 지폐 한 장과 50루피 지폐 한 장의 조합으로 거스름돈을 줍니다. 이 조합이 불가능하면 50루피 지폐 세 장으로 거스름돈을 줍니다. 둘 다 불가능하다면 판매에 실패합니다.
200루피를 받았을 때 100루피+50루피 조합을 우선적으로 사용하는 것이 중요합니다. 50루피 세 장을 아껴두면 이후 100루피를 낸 고객에게도 대응할 수 있기 때문입니다.
알고리즘 단계
- 지폐별 개수를 저장할 빈 맵 freq를 준비합니다.
- 인덱스 i를 0으로 초기화합니다.
- i가 notes의 길이보다 작은 동안 다음을 반복합니다.
- notes[i]가 50이면 freq[50]을 1 증가시킵니다.
- notes[i]가 100이면 freq[100]을 1 증가시키고, freq[50]이 0이면 반복문을 종료합니다. 그렇지 않으면 freq[50]을 1 감소시킵니다.
- notes[i]가 200이면, freq[100] > 0이고 freq[50] > 0일 때 두 값을 각각 1씩 감소시킵니다. 그렇지 않고 freq[50] >= 3이면 freq[50]을 3 감소시킵니다. 어느 쪽도 아니면 반복문을 종료합니다.
- 반복이 끝난 후 i가 notes의 길이와 같으면 True를 반환하고, 그렇지 않으면 False를 반환합니다.
구현 예제
아래 구현을 통해 더 잘 이해해 보겠습니다.
from collections import defaultdict
def solve(notes):
freq = defaultdict(int)
i = 0
while i < len(notes):
if notes[i] == 50:
freq[50] += 1
elif notes[i] == 100:
freq[100] += 1
if freq[50] == 0:
break
freq[50] -= 1
else:
if freq[100] > 0 and freq[50] > 0:
freq[100] -= 1
freq[50] -= 1
elif freq[50] >= 3:
freq[50] -= 3
else:
break
i += 1
if i == len(notes):
return True
return False
notes = [50, 50, 100, 100]
print(solve(notes))
입력
[50, 50, 100, 100]
출력
True
복잡도 분석
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 지폐 종류가 세 가지로 고정되어 있어 공간 복잡도는 O(1)입니다. 따라서 대기열의 길이가 길어져도 효율적으로 동작합니다.