99클럽 코테 스터디 26일차 1475. Final Prices With a Special Discount in a Shop

1475. Final Prices With a Special Discount in a Shop

 

https://leetcode.com/problems/final-prices-with-a-special-discount-in-a-shop/

 

다음과 같은 문제가 주어집니다: 정수 배열 prices가 주어집니다. 여기서 prices[i]는 가게에서 i번째 항목의 가격을 나타냅니다.

가게에서는 항목에 대해 특별 할인 정책을 제공합니다. 만약 i번째 항목을 구매하면, j번째 항목의 가격에 해당하는 할인을 받게 됩니다. 여기서 j는 i보다 크고(j > i), 가격이 i번째 항목의 가격보다 작거나 같은(prices[j] <= prices[i]) 최소 인덱스입니다. 만약 이러한 j를 찾을 수 없다면, 할인을 받지 못합니다.

 

각 항목에 대해 최종 지불할 가격을 반환하는 정수 배열 answer를 반환하세요. answer[i]는 i번째 항목의 최종 지불 가격을 나타냅니다.

 

 

풀이

 

class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        # 결과를 담을 배열을 prices로 초기화
        answer = prices[:]
        stack = []
        
        # 배열을 순회하면서
        for i in range(len(prices)):
            # 스택이 비어있지 않고, 현재 가격이 스택의 마지막 가격보다 작거나 같으면
            while stack and prices[stack[-1]] >= prices[i]:
                # 해당 인덱스에 대한 할인을 현재 가격으로 적용
                index = stack.pop()
                answer[index] -= prices[i]
            # 현재 인덱스를 스택에 추가
            stack.append(i)
        
        return answer