[LeetCode] Final Prices With a Special Discount in a Shop

1.문제

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.

가격이 적혀있는 배열이 주어진다. 현재 index보다 큰 index의 값중에 첫번째 작은가격의 값으로 현재 값을 할인 받는다면 최종 할인된 가격배열을 리턴하는 문제이다.

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]

Constraints:

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

2.풀이

1. prices.length - 1 만큼 prices 를 순회한다.
2. 현재 prices와 다음 인덱스부터 시작해서 prices를 순회하여 가격을 하나하나 비교한다.
3. 만약 prices[i] >= prices[j] 라면 prices[i] -= prices[j]

/**
 * @param {number[]} prices
 * @return {number[]}
 */
const finalPrices = function (prices) {
  for (let i = 0; i < prices.length - 1; i++) { // prices 순회
    for (let j = i + 1; j < prices.length; j++) { // j > i 인 prices 중 prices[i] >= prices[j] 이면 prices[i]에서 prices[j] 만큼 빼주기
      if (prices[i] >= prices[j]) {
        prices[i] -= prices[j];
        break;
      }
    }
  }

  return prices;
};

3.결과