[Leetcode] 1833. Maximum Ice Cream Bars

문제 요약

• 알고리즘 분류:  그리디, 계수 정렬
• 난이도: Medium
• 문제내용:
  • 각 아이스크림 바의 가격은 costs 배열에 저장되어 있습니다. 소년은 처음에 coins 코인을 가지고 있으며, 가능한 많은 아이스크림 바를 구매하고 싶어합니다.
  • 주어진 coins 코인으로 소년이 살 수 있는 최대 아이스크림 바의 개수를 반환해야 한다.
• 사이트 주소: https://leetcode.com/problems/maximum-ice-cream-bars/description/

 

문제풀이

 이번 문제에서는 완전탐색으로 풀수 있지만 최대 크기가 10^5인점으로 고려하면 다른 방법으로 풀어야 한다. 그래서 이번에는 그리디나 계수정렬로 풀어야 한다. 그에 대한 이론 설명은 아래 글에 확인 해보면 된다.

• 그리디: https://jih3508.tistory.com/70
• 계수 정렬 : https://jih3508.tistory.com/271

문제 접근 방법

 완전 탐색으로는 시간 초과나 가서 그리디나 계수 정렬 방법으로 해결 해야 한다.  위 문제는 구현 보다는 아이디어가 중요하다 그래서 어떻게 접근 하는지에 집중만 하면 어렵지 않다. 문제를 하기 전에 우리가 집중적으로 봐야 할 내용은 최대한 많은 아이스크림을 사기 위해서는 가장 저렴한 아이스크림부터 구매하는 것이다.

따라서 우리의 해결 방법은 다음과 같다:

1. 아이스크림 가격 배열을 오름차순으로 정렬합니다.
2. 정렬된 배열을 순회하면서 가장 저렴한 아이스크림부터 구매합니다.
3. 각 구매 후에 남은 코인을 계산하고, 더 이상 구매할 수 없을 때까지 반복합니다.

마무리

 위와 같이 구현했을때 2가지 요건을 봐야 한다. 그리디로 하면 정렬 때문에 시간 복잡도는 O(nlogn)이고 계수 정렬은 O(n)만큼 나온다. 문제는 그리디 알고리즘의 전형적인 예시로, 최적의 해결책을 찾기 위해 '지금 당장 최선의 선택'을 반복하는 방식입니다. 아이스크림 바를 가장 저렴한 것부터 구매함으로써, 주어진 코인으로 최대한 많은 아이스크림을 살 수 있다. 이러한 유형의 문제는 코딩 인터뷰에서 자주 등장하므로, 그리디 접근법과 정렬 알고리즘의 특성을 잘 이해하고 있어야 한다. 또한 문제의 제약 조건에 따라 적절한 정렬 방법(기본 정렬 또는 계수 정렬)을 선택하는 것이 중요하다.

Code

 이번에는 그리디와 계수정렬로 푼것 각각 보여 줄것이다.

그리디(Greedy)

Python

class Solution:
    def maxIceCream(self, costs: List[int], coins: int) -> int:
        count = 0 # 구매할 수 있는 아이스크림 바의 개수
        # 아이스크림 바 가격을 오름차순으로 정렬
        costs.sort()

        # 정렬된 가격 배열을 순회하며 구매 가능한 아이스크림 확인
        for cost in costs:
            # 현재 아이스크림 가격이 남은 코인보다 크면 더 이상 구매 불가능
            if cost > coins:
                break
            # 이스크림을 구매하고 남은 코인에서 가격을 차감
            coins -= cost
            # 매한 아이스크림 개수 증가
            count += 1

        return count

Java

class Solution {
    public int maxIceCream(int[] costs, int coins) {
        int count = 0;  // 구매할 수 있는 아이스크림 바의 개수

        // 아이스크림 바 가격을 오름차순으로 정렬
        Arrays.sort(costs);

        // 정렬된 가격 배열을 순회하며 구매 가능한 아이스크림 확인
        for(int cost : costs) {
            // 현재 아이스크림 가격이 남은 코인보다 크면 더 이상 구매 불가능
            if(cost > coins) {
                break;
            }
            // 아이스크림을 구매하고 남은 코인에서 가격을 차감
            coins-=cost;
            // 구매한 아이스크림 개수 증가
            count++;
        }


        return count;
    }
}

Javascript

var maxIceCream = function(costs, coins) {
    let count = 0;  // 구매할 수 있는 아이스크림 바의 개수

    // 아이스크림 바 가격을 오름차순으로 정렬
    costs.sort((a, b) => a - b);

    // 정렬된 가격 배열을 순회하며 구매 가능한 아이스크림 확인
    costs.some(cost => {
        // 현재 아이스크림 가격이 남은 코인보다 크면 더 이상 구매 불가능
        if(cost > coins){
            return true;
        }
        coins -= cost; // 아이스크림을 구매하고 남은 코인에서 가격을 차감
        count++; // 구매한 아이스크림 개수 증가
        return false;
    })

    return count;
};

계수 정렬(Counting Sort)

Python

class Solution:
    def maxIceCream(self, costs: List[int], coins: int) -> int:
        max_cost = max(costs)
        # 가격별 아이스크림 개수를 저장
        counts = [0 for _ in range(max_cost + 1)]
        for cost in costs:
            counts[cost] += 1



        count = 0 # 구매할 수 있는 아이스크림 바의 개수
        cost = 1
        while cost <= max_cost and cost <= coins:

            if counts[cost] != 0:
                num_ice_cream = min(counts[cost], coins // cost)
                coins -= num_ice_cream * cost
                count += num_ice_cream

            cost += 1

        return count

Java

class Solution {
    public int maxIceCream(int[] costs, int coins) {
         int maxCost = Arrays.stream(costs).max().getAsInt(); // 가장 비싼 아이스크림 가격 찾기

        // 가격별 아이스크림 개수를 저장
        int[] counts = new int[maxCost + 1];
        for(int cost : costs) {
            counts[cost]++;
        }

        int count = 0;
        // 가장 저렴한 가격부터 순회
        for(int cost = 1; cost <= maxCost && cost <= coins; cost++) {
            if(counts[cost] != 0) {
                // 현재 가격의 아이스크림을 최대한 많이 구매
                int numIceCream = Math.min(counts[cost], coins / cost);
                coins -= numIceCream * cost;
                count += numIceCream;
            }
        }

        return count;
    }
}

Javascript

 

var maxIceCream = function(costs, coins) {

    const maxCost = Math.max.apply(Math, costs);

    // 가격별 아이스크림 개수를 저장
    let counts = Array(maxCost + 1).fill(0);
    costs.forEach(cost => {
        counts[cost]++;
    });

    let count = 0;  // 구매할 수 있는 아이스크림 바의 개수

    // 가장 저렴한 가격부터 순회
    for(let cost = 1; cost <= maxCost && cost <= coins; cost++) {
        if(counts[cost] != 0) {
            // 현재 가격의 아이스크림을 최대한 많이 구매
            const numIceCream = Math.min(counts[cost], Math.floor(coins / cost));
            coins -= numIceCream * cost;
            count += numIceCream;
        }
    }

    return count;
};