[LeetCode] - 2706. Buy Two Chocolates

LeetCode

[LeetCode] - 2706. Buy Two Chocolates

로공컴재이 2024. 8. 2. 16:26

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Buy Two Chocolates" 문제입니다.

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

문제 :

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.

Example 1 :

Input : prices = [1,2,2], money = 3

Output : 0

Explanation : Purchase the chocolates priced at 1 and 2 units respectively.

You will have 3 - 3 = 0 units of money afterwards.

Thus, we return 0.

Example 2 :

Input : prices = [3,2,3], money = 3

Output : 3

Explanation : You cannot buy 2 chocolates without going in debt, so we return 3.

Constraints :

2 <= prices.length <= 50
1 <= prices[i] <= 100
1 <= money <= 100

주어진 문제는 다양한 가격의 초콜릿을 판매하는 가게에서 두 개의 초콜릿을 구매하는 방법을 찾는 것입니다. 초기 금액 money를 가지고 있으며, 두 개의 초콜릿을 구매한 후 남은 금액이 비부정이어야 합니다. 초콜릿 두 개의 가격 합을 최소화하여 초콜릿을 구매하는 것이 목표입니다.

만약, 두 개의 초콜릿을 구매할 수 없는 경우(초과 지출이 발생하는 경우), 초기 금액인 money를 반환해야 합니다.

class Solution {
    public int buyChoco(int[] prices, int money) {
        Arrays.sort(prices);
        if (prices[0] + prices[1] <= money) return money - (prices[0] + prices[1]);
        return money;
    }
}

이 코드는 주어진 초콜릿 가격 배열 prices에서 가장 저렴한 두 개의 초콜릿을 구매할 수 있는지를 판단하고, 구매할 수 있다면 남은 금액을 반환하는 알고리즘을 구현합니다.

초콜릿 가격 정렬 :
- 초콜릿 가격 배열 prices를 오름차순으로 정렬합니다. 이를 통해 가장 저렴한 두 개의 초콜릿을 쉽게 선택할 수 있습니다.
저렴한 두 초콜릿의 합 계산 및 조건 검사 :
- 정렬된 배열의 첫 번째와 두 번째 요소의 합을 계산하여, 이 값이 초기 금액 money보다 작거나 같은지 확인합니다.
- 두 초콜릿의 합이 money보다 작거나 같으면 두 초콜릿을 구매할 수 있으므로 남은 금액 money - (prices[0] + prices[1])을 반환합니다.
구매 불가능한 경우 :
- 만약 두 초콜릿의 합이 money보다 크면, 두 초콜릿을 구매할 수 없으므로 초기 금액 money를 그대로 반환합니다.

시간 복잡도

O(nlog n) : 주어진 배열을 정렬하는 데 소요되는 시간입니다. 여기서 n은 배열 prices의 길이입니다.
- Arrays.sort()는 평균적으로 O(n \log n) 시간 복잡도를 가집니다.

공간 복잡도

O(1) : 추가적인 배열이나 데이터 구조를 사용하지 않고, 입력 배열 자체를 정렬하기 때문에 상수 공간 복잡도를 가집니다.
- 정렬 자체가 배열 내에서 이루어지므로 추가적인 공간이 필요하지 않습니다.

제 코드는 2 ms 결과인 코드인데요, 이것보다 더 빠른 코드가 있대서 다른 유저 코드를 인용해왔습니다 :

class Solution {
    public int buyChoco(int[] prices, int money) {
   

    // SOLUTION 2
    //TIME COMPLEXITY = O(N)
    int min1=Integer.MAX_VALUE;
    int min2=Integer.MAX_VALUE;
    for(int x:prices)
    {
       if(x<min1)
       {
           min2=min1;
           min1=x;
       }
       else if(x<min2) 
        min2=x;
    }
    if(min1+min2 <= money) return money-(min1+min2);
    return money;
    
     }
}

// anshikac2307 유저의 코드

이 코드는 주어진 초콜릿 가격 배열 prices에서 두 개의 가장 저렴한 초콜릿을 선택하고, 초기 금액 money로 구매할 수 있는지를 판단합니다. 정렬 없이 두 최저 값을 찾는 방법을 사용하여 시간 복잡도를 O(n)으로 줄였습니다.

최저값 변수 초기화 :
- min1과 min2를 각각 Integer.MAX_VALUE로 초기화합니다. 이는 가장 작은 두 값을 찾기 위한 준비 단계입니다.
최저값 탐색 :
- prices 배열을 순회하면서 각 초콜릿 가격 x를 검사합니다.
- 만약 x가 min1보다 작으면 min2를 min1로 업데이트하고, min1을 x로 업데이트합니다. 이는 새로운 최저값을 찾았다는 의미입니다.
- 그렇지 않고 x가 min2보다 작으면 min2를 x로 업데이트합니다. 이는 min1보다는 크지만, 두 번째로 작은 값이라는 의미입니다.
구매 가능 여부 판단 :
- 가장 작은 두 초콜릿 가격의 합 min1 + min2가 초기 금액 money보다 작거나 같으면, 남은 금액을 반환합니다.
- 그렇지 않으면, 두 초콜릿을 구매할 수 없으므로 초기 금액 money를 그대로 반환합니다.