Python에서 다른 메모로 고객 대기열을 제공할 수 있는지 확인

Notes라는 배열이 대기열에 있는 고객이 보유하고 있는 다른 루피 지폐를 나타낸다고 가정합니다. 그들은 모두 Rs 50 상당의 티켓을 사기 위해 기다리고 있습니다. 여기에 가능한 메모는 [50, 100 및 200]입니다. 사람들에게 순서대로 티켓을 판매할 수 있는지 여부를 확인해야 합니다. 처음에는 0루피가 손에 있습니다.

따라서 입력이 notes =[50, 50, 100, 100]과 같은 경우 출력은 처음 두 개에 대해 True가 될 것이며 아무 것도 반환할 필요가 없지만 이제 두 개의 Rs 50 메모가 있습니다. 따라서 마지막 2개에 대해 Rs 50 메모를 반환하고 모든 티켓을 순서대로 판매할 수 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• freq :=빈 지도
• i :=0
• 내가 <음표의 크기인 동안
  • 메모[i]가 50과 같으면
    • 주파수[50] :=주파수[50] + 1
  • 그렇지 않으면 notes[i]가 100과 같을 때
    • 주파수[100] :=주파수[100] + 1
    • freq[50]이 0이면
      • 루프에서 나오다
    • 주파수[50] :=빈도[50] - 1
  • 그렇지 않으면
    • freq[100]> 0이고 freq[50]> 0이면
      • 주파수[100] :=주파수[100] - 1
      • 주파수[50] :=빈도[50] - 1
    • 그렇지 않으면 freq[50]>=3일 때
      • 주파수[50] :=빈도[50] - 3
    • 그렇지 않으면
      • 루프에서 나오다
  • 나는 :=나는 + 1
• i가 음표의 크기와 같으면
  • 참 반환
• 거짓을 반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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