860. 레모네이드 변경

난이도: 쉬움

주제: 배열, 탐욕

레모네이드 가판대에서는 각 레모네이드 가격이 5달러입니다. 고객은 귀하로부터 제품을 구매하고 한 번에 하나씩 주문하기 위해(청구서에 지정된 순서대로) 줄을 서 있습니다. 각 고객은 레모네이드 하나만 구매하고 5달러, 10달러 또는 20달러 지폐로 지불합니다. 순 거래에서 고객이 $5를 지불하도록 각 고객에게 올바른 잔돈을 제공해야 합니다.

참고 처음에는 거스름돈이 없습니다.

bills[i]가 i^번째 고객이 지불하는 청구서인 정수 배열 청구서가 주어지면 모든 고객에게 올바른 변경 사항을 제공할 수 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다. .

예 1:

• 입력: 청구서 = [5,5,5,10,20]
• 출력: 참
• 설명:
  • 선착순 3명의 고객 중 5달러 지폐 3장을 순서대로 수집합니다.
  • 네 번째 고객으로부터 10달러 지폐를 모아 5달러를 돌려드립니다.
  • 5번째 고객부터는 10달러 지폐와 5달러 지폐를 드립니다.
  • 모든 고객이 올바른 변경사항을 받았으므로 true를 출력합니다.

예 2:

• 입력: 청구서 = [5,5,10,10,20]
• 출력: 거짓
• 설명:
  • 순서대로 처음 2명의 고객으로부터 5달러 지폐 2장을 수집합니다.
  • 다음 주문 고객 2명을 위해 10달러 지폐를 모아 5달러 지폐를 돌려드립니다.
  • 마지막 고객님께는 10달러 지폐가 2장 밖에 없기 때문에 잔돈 15달러를 돌려드릴 수 없습니다.
  • 모든 고객이 올바른 변경사항을 수신한 것은 아니므로 답변은 거짓입니다.

제약조건:

• 5
• bills[i]는 5, 10 또는 20입니다.

해결책:

고객이 지불하는 데 사용하는 청구서를 기반으로 고객에게 변경 사항을 제공하는 프로세스를 시뮬레이션해야 합니다. 중요한 것은 가지고 있는 5달러 및 10달러 지폐의 수를 추적하는 것입니다. 이는 더 큰 지폐에 잔돈을 제공하는 데 필요하기 때문입니다.

이 솔루션을 PHP로 구현해 보겠습니다: 860. 레모네이드 변경

설명:

1. 초기화: $5와 $10을 0으로 설정하여 시작합니다. 이는 우리가 가지고 있는 $5와 $10 지폐의 수를 나타냅니다.

2. 각 청구서 처리:

   • 고객이 5달러 지폐로 결제하는 경우: 단순히 5달러 지폐의 개수를 늘립니다.
   • 고객이 10달러 지폐로 결제하는 경우: 5달러 지폐 1장을 거스름돈으로 돌려주어야 하므로 5달러 지폐 수를 줄이고 10달러 지폐 수를 늘립니다. 5달러 지폐가 없으면 false를 반환합니다.
   • 고객이 20달러 지폐로 결제하는 경우: 잔돈으로 10달러 지폐 1장과 5달러 지폐 1장을 우선적으로 제공합니다. 그것이 가능하지 않다면, 우리는 5달러짜리 지폐 세 장을 주려고 노력합니다. 두 옵션 모두 사용할 수 없으면 false를 반환합니다.

3. 최종 확인: 변경 사항 없이 모든 고객을 성공적으로 처리한 경우 true를 반환합니다.

엣지 케이스:

• 이 기능은 필요한 5달러 지폐를 준비하지 않은 채 10달러 또는 20달러 지폐를 너무 일찍 받은 경우와 같이 정확한 잔돈을 제공하는 것이 불가능한 시나리오를 처리해야 합니다.
• 제약으로 인해 큰 입력 크기(최대 100,000명의 고객)를 효율적으로 처리해야 합니다. 솔루션은 O(n) 시간 복잡도로 실행되므로 이 문제에 최적입니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이와 같이 더 유용한 콘텐츠를 원하시면 언제든지 저를 팔로우하세요.

• 링크드인
• GitHub