[LeetCode] 2706. Buy Two Chocolates

https://leetcode.com/problems/buy-two-chocolates/

Buy Two Chocolates - LeetCode

leetcode - Buy Two Chocolates

문제 유형 : 배열, 구현

문제 난이도 : Easy

 

문제

You are given an integer array prices representing the prices of various chocolates in a store. You are also given a single integer money, which represents your initial amount of money.

You must buy exactly two chocolates in such a way that you still have some non-negative leftover money. You would like to minimize the sum of the prices of the two chocolates you buy.

Return the amount of money you will have leftover after buying the two chocolates. If there is no way for you to buy two chocolates without ending up in debt, return money. Note that the leftover must be non-negative.

 

당신은 정수 배열 prices를 받는다. 상점의 다양한 초콜릿들의 각 값을 나타낸다.

당신은 money정수를 받는다. 당신의 초기 소지금이다.

 

당신은 정확히 2개의 초콜릿을 사야한다. 남는 돈이 음수가 되면 안되고, 당신은 최소한의 비용을 들여서 사려고 한다.

만약 초콜릿을 두 개 살 수 없다면, money를 반환하고, 아니라면 남는 잔돈을 반환한다.

잔돈이 음수가 되면 안된다는 걸 명심하라.

 

풀이

O(nlogn)풀이: 배열을 정렬하고, 0번째와 1번째 인덱스를 더한다. 더한 값이 money보다 크면 money를 반환하고, 작으면 money에서 뺀 값을 반환하라.

 

O(n)풀이: 배열의 한 원소씩 순회하면서, 가장 싼 초콜릿과 그 다음으로 싼 초콜릿을 갱신시킨다. 더한 값이 money보다 크면 money를 반환하고, 작으면 money에서 뺀 값을 반환하라.

 

 

코드

C++(O(n)풀이로 도전!)

static const int __ = []() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int buyChoco(vector<int>& prices, int money) {
        int minimum = 1e9;
        int secondary = 1e9;

        for(const auto &price : prices) {
            if(minimum > price) {
                secondary = minimum;
                minimum = price;
            } else if(secondary > price) {
                secondary = price;
            }
        }
        int sum = minimum + secondary;

        return sum > money? money : money-sum;
    }
};