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

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

leetcode - Final Prices With a Special Discount in a Shop

문제 유형: 구현

문제 난이도: 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.

 

정수 배열 prices를 받는다.

prices[i]를 살때, i < j이고 prices[i] >= prices[j]인 최초의 인덱스 j를 골라서 그 가격만큼 할인받을 수 있다.

answer[i]에 실제 i번물건을 살때의 가격을 구하시오.

 

풀이

그래도 구현해주면 된다. i < j이고 prices[i] >= prices[j]인 최초의 인덱스 j를 찾아서 prices[j]만큼 빼주면 된다.

 

코드

C++

class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        int n = prices.size();
        vector<int> ans(n);

        for(int i = 0; i < n; ++i) {
            int price = prices[i];
            for(int j = i+1; j < n; ++j) {
                if(prices[j] <= price) {
                    price -= prices[j];
                    break;
                }
            }
            ans[i] = price;
        }

        return ans;
    }
};