[LeetCode] 1475. Final Prices With a Special Discount in a Shop (Python)

 

난이도: Easy

문제 설명

---

You are given an integer array prices where prices[i] is the price of the ith item in a shop.

 

There is a special discount for items in the shop. If you buy the ith item, then you will receive a discount equivalent to prices[j] where j is the minimum index such that j > i and prices[j] <= prices[i]. Otherwise, you will not receive any discount at all.

 

Return an integer array answer where answer[i] is the final price you will pay for the ith item of the shop, considering the special discount.

 

문제 예제

---

Example 1:

Input: prices = [8,4,6,2,3]
Output: [4,2,4,2,3]
Explanation:
For item 0 with price[0]=8 you will receive a discount equivalent to prices[1]=4, therefore, the final price you will pay is 8 - 4 = 4.
For item 1 with price[1]=4 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 4 - 2 = 2.
For item 2 with price[2]=6 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 6 - 2 = 4.
For items 3 and 4 you will not receive any discount at all.

Example 2:

Input: prices = [1,2,3,4,5]
Output: [1,2,3,4,5]
Explanation: In this case, for all items, you will not receive any discount at all.

Example 3:

Input: prices = [10,1,1,6]
Output: [9,0,1,6]

 

제한 사항

---

• 1 <= prices.length <= 500
• 1 <= prices[i] <= 1000

 

✏️ Solution(솔루션)

---

class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        n = len(prices)

        for i in range(n):
            for j in range(i+1, n):
                if prices[i] >= prices[j]:
                    prices[i] -= prices[j]
                    break

        return prices

 

제한사항을 보니 input 데이터가 크지 않아 단순히 Brute Force방법으로 풀었다.

 

다른 사람들의 풀이를 보니 나처럼 brute force로 푼 사람도 있고 stack을 이용해 푼 사람도 있는 것 같다.

 

stack을 사용해서도 한번 풀어봐야될 것 같다.

---

1475. Final Prices With a Special Discount in a Shop