매장 특별 할인이 포함된 최종 가격

1475. 매장 특별 할인으로 최종 가격

난이도: 쉬움

주제: 배열, 스택, 단조 스택

가격[i]이 상점의 i^번째 품목 가격인 정수 배열 가격이 주어졌습니다.

상점 내 상품에 대한 특별 할인이 진행됩니다. i^번째 항목을 구매하면 가격[j]과 동일한 할인을 받게 됩니다. 여기서 j는 j > i 및 가격[j] <= 가격[i]. 그렇지 않으면 어떠한 할인도 받을 수 없습니다.

정수 배열 답변을 반환합니다. 여기서 답변[i]는 특별 할인을 고려하여 상점의 i^번째 품목에 대해 지불할 최종 가격입니다.

예 1:

• 입력: 가격 = [8,4,6,2,3]
• 출력: [4,2,4,2,3]
• 설명:
  • 가격[0]=8인 항목 0의 경우 가격[1]=4에 해당하는 할인을 받게 되므로 지불할 최종 가격은 8 - 4 = 4입니다.
  • 가격[1]=4인 항목 1의 경우 가격[3]=2에 해당하는 할인을 받게 되므로 지불할 최종 가격은 4 - 2 = 2입니다.
  • 가격[2]=6인 항목 2의 경우 가격[3]=2에 해당하는 할인을 받게 되므로 지불할 최종 가격은 6 - 2 = 4입니다.
  • 3번, 4번 항목은 할인이 전혀 적용되지 않습니다.

예 2:

• 입력: 가격 = [1,2,3,4,5]
• 출력: [1,2,3,4,5]
• 설명: 이 경우 모든 상품에 대해 일체 할인을 받으실 수 없습니다.

예 3:

• 입력: 가격 = [10,1,1,6]
• 출력: [9,0,1,6]

제약조건:

• 1 <= 가격.길이 <= 500
• 1 <= 가격[i] <= 1000

힌트:

1. 무차별 대입: 루프가 있는 상점의 i번째 항목에 대해 조건을 만족하는 첫 번째 위치 j를 찾아 할인을 적용합니다. 그렇지 않으면 할인은 0입니다.

해결책:

현재 가격보다 가격이 낮거나 같은 최신 품목이 있다는 조건에 따라 특별 할인을 적용해야 하며, 무차별 접근 방식을 사용할 수 있습니다. 가격 배열을 반복하고 각 항목에 대해 가격이 더 낮거나 같은 첫 번째 항목을 찾습니다. 이는 중첩 루프를 사용하여 달성할 수 있습니다. 스택을 활용하면 효율적으로 품목 가격을 추적하고 특별 할인을 적용할 수 있습니다.

접근하다:

1. 스택 접근 방식:

   • 가격 배열을 왼쪽에서 오른쪽으로 반복할 수 있습니다. 각 항목에 대해 스택을 사용하여 아직 할인을 찾지 못한 가격을 추적합니다.
   • 각 가격에 대해 스택 상단의 가격보다 작거나 같은지 확인합니다. 그렇다면 할인을 적용할 수 있다는 뜻입니다.
   • 스택은 항목의 인덱스를 저장하며, 각 항목에 대해 현재 가격이 스택의 인덱스 가격보다 높은지 확인합니다. 즉, 할인이 없음을 의미합니다. 그렇지 않은 경우에는 현재 가격에서 해당 가격을 빼서 할인을 적용하세요.

2. 엣지 케이스: 배열 내에서 더 낮은 가격의 품목이 없으면 할인이 적용되지 않습니다.

PHP에서 이 솔루션을 구현해 보겠습니다. 1475. 매장 특별 할인으로 최종 가격

  
  
  설명:




초기화:


$prices와 동일한 크기의 $result 배열을 만들고 0으로 초기화합니다.



외부 루프:


인덱스 $i의 각 가격을 반복하여 할인 후 최종 가격을 계산합니다.



내부 루프:


각 가격 $i에 대해 후속 가격 $j를 반복합니다(여기서 $j > $i).
$prices[$j]가 $prices[$i]보다 작거나 같은지 확인하세요. true인 경우 $discount = $prices[$j]를 설정하고 내부 루프를 종료합니다.



최종 가격 계산:


$prices[$i]에서 찾은 할인을 빼고 결과를 $result[$i]에 저장합니다.



반품 결과:


모든 가격을 처리한 후 최종 결과 배열을 반환합니다.





  
  
  복잡성:




시간 복잡도: O(n²)(각 가격에 대한 중첩 루프로 인해).

공간 복잡도: O(n)(결과 배열의 경우).



  
  
  예제 출력:



가격 = [8, 4, 6, 2, 3]의 경우 출력은 [4, 2, 4, 2, 3]입니다.
가격 = [1, 2, 3, 4, 5]의 경우 출력은 [1, 2, 3, 4, 5]입니다.
가격 = [10, 1, 1, 6]의 경우 출력은 [9, 0, 1, 6]입니다.


이 접근 방식은 가장 최적화된 솔루션은 아니지만 문제의 제약 조건(1 <= 가격.길이 <= 500) 내에서 작동합니다.

연락처 링크

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

이런 유용한 콘텐츠를 더 원하시면 저를 팔로우해주세요.


링크드인
깃허브



          

            
  

            
        
위 내용은 매장 특별 할인이 포함된 최종 가격의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!