[LeetCode/Easy] 1475. Final Prices With a Special Discount in a Shop

1. Input

1) int 배열 prices

- prices[i]에는 i번째 물건의 가격이 담겨있다.

 

2. Output

1) 아래 규칙대로 할인받았을 때 지불해야 할 금액이 담긴 배열

// 규칙

- i번째 물건을 산다면, price[j]만큼 할인받는다.

- 이때 price[j]<=price[i]여야 한다.

- j는 i보다 큰 인덱스 중 위 조건을 만족하는 가장 작은 인덱스다.

 

3. Constraint

1) 1 <= prices.length <= 500

2) 1 <= prices[i] <= 1000

 

4. Example

Input: prices = [8,4,6,2,3] -> Output: [4,2,4,2,3]

설명:

- 0번째: 가격이 8보다 저렴한 것은 4, 6, 2, 3 -> 인덱스는 1, 2, 3, 4 -> 가장 작은 인덱스는 1이므로 8-4=4를 지불한다.

- 1번째: 가격이 4보다 저렴한 것은 2, 3 -> 인덱스는 3, 4 -> 가장 작은 인덱스는 3이므로 4-2=2를 지불한다.

- 2번째: 가격이 6보다 저렴한 것은 2, 3 -> 인덱스는 3, 4 -> 가장 작은 인덱스는 3이므로 6-2=4를 지불한다.

- 3번째: 가격이 2보다 저렴한 것은 없으므로 2를 지불한다.

- 4번째: 가격이 3보다 저렴한 것은 없으므로 3를 지불한다.

 

5. Code

1) 첫 코드(2022/06/16)

for(int i=0 ; i<prices.length-1 ; i++){
    for(int j=i+1 ; j<prices.length ; j++){
        if(prices[i] >= prices[j]){
            prices[i] -= prices[j];
            break;
        }
    } // for j
} // for i

return prices;