[리트코드] 1833 - Maximum Ice Cream Bars

1833. Maximum Ice Cream Bars

Medium

---

It is a sweltering summer day, and a boy wants to buy some ice cream bars.

At the store, there are n ice cream bars. You are given an array costs of length n, where costs[i] is the price of the ith ice cream bar in coins. The boy initially has coins coins to spend, and he wants to buy as many ice cream bars as possible. 

Note: The boy can buy the ice cream bars in any order.

Return the maximum number of ice cream bars the boy can buy with coins coins.

You must solve the problem by counting sort.

 

Example 1:

Input: costs = [1,3,2,4,1], coins = 7
Output: 4
Explanation: The boy can buy ice cream bars at indices 0,1,2,4 for a total price of 1 + 3 + 2 + 1 = 7.

Example 2:

Input: costs = [10,6,8,7,7,8], coins = 5
Output: 0
Explanation: The boy cannot afford any of the ice cream bars.

Example 3:

Input: costs = [1,6,3,1,2,5], coins = 20
Output: 6
Explanation: The boy can buy all the ice cream bars for a total price of 1 + 6 + 3 + 1 + 2 + 5 = 18.

 

Constraints:

• costs.length == n
• 1 <= n <= 105
• 1 <= costs[i] <= 105
• 1 <= coins <= 108

---

문제 풀이

문제 분석

이 문제는 주어진 동전(coins)으로 살 수 있는 아이스크림의 최대 개수를 구하는 문제입니다.
입력은 아이스크림 가격 배열 costs와 소지한 동전 수 coins이며, 출력은 구매 가능한 최대 아이스크림 개수(int)입니다.
아이스크림은 순서에 상관없이 구매할 수 있으므로, 가장 저렴한 것부터 순서대로 구매하는 그리디(Greedy) 전략이 최적입니다. 단, 문제 제약 조건에 "You must solve the problem by counting sort"라고 명시되어 있어 정렬 대신 카운팅 정렬을 활용해야 합니다.

---

접근 방법

카운팅 정렬(Counting Sort) + 그리디(Greedy) 방식을 사용합니다.

• 이유: costs[i]의 최댓값이 100,000(10^5)으로 비교적 작습니다. 일반적인 정렬(O(N log N))을 써도 되지만, 문제 요구사항대로 카운팅 정렬을 사용하면 가격별 개수를 O(N + M)에 셀 수 있습니다(M = 최대 가격). 가격이 낮은 것부터 순회하며 살 수 있는 만큼 사면 되므로 그리디가 성립합니다.
• 자료구조: 가격별 개수를 저장할 배열 C (크기: max_cost + 1)

---

구현 설명

1단계: 가격별 개수 세기 (카운팅 정렬의 Count 단계)

• costs 배열의 최댓값 max_cost를 구해 크기가 max_cost + 1인 배열 C를 생성합니다.
• costs를 순회하며 각 가격 costs[i]에 해당하는 인덱스 C[costs[i]] 값을 1 증가시킵니다.
• 이제 C[price]는 price원 짜리 아이스크림의 개수를 의미합니다.

2단계: 저렴한 가격부터 순회하며 구매하기

• 가격 i를 1부터 max_cost까지 오름차순으로 순회합니다.
• C[i] == 0이면 해당 가격의 아이스크림이 없으므로 건너뜁니다(continue).

3단계: 현재 가격으로 살 수 있는 최대 개수 계산 및 상태 갱신

• 현재 가격 i로 살 수 있는 최대 개수는 min(보유 개수 C[i], coins // i)입니다. 이를 can_buy에 저장합니다.
• 총 금액에서 구매 비용(can_buy * i)을 차감하고(coins -= ...), 구매 개수를 누적합니다(count += can_buy).

4단계: 조기 종료 조건 확인

• 구매 후 남은 동전 coins가 현재 가격 i보다 작으면, 이후 더 비싼 아이스크림은 절대 살 수 없으므로 반복문을 종료합니다(break).
• 최종적으로 누적된 count를 반환합니다.

---

⏱복잡도 분석

• 시간 복잡도: O(N + M)
  • N: costs 배열의 길이 (최대 10^5)
  • M: costs의 최댓값 (최대 10^5)
  • 개수 세기: O(N), 가격 순회 및 구매 로직: O(M) → 총 O(N + M)
• 공간 복잡도: O(M)
  • 카운팅 배열 C의 크기가 M + 1이므로 O(M) 공간을 사용합니다.

---

핵심 포인트

1. 가격 오름차순 구매가 최적: 비싼 것보다 싼 것을 먼저 사야 개수를 최대로 늘릴 수 있습니다(그리디 선택 속성).
2. 카운팅 정렬로 정렬 대체: 가격 범위(10^5)가 제한되어 있어, O(N log N) 정렬 대신 O(N + M) 카운팅 정렬로 가격순 정렬 효과를 냅니다.
3. 조기 종료로 불필요한 연산 방지: 남은 돈으로 현재 가격을 살 수 없으면(coins < i), 더 비싼 가격도 살 수 없으므로 루프를 즉시 종료하여 효율을 높입니다.

풀이 코드

class Solution:
    def maxIceCream(self, costs: List[int], coins: int) -> int:
        max_cost = max(costs)
        C = [0] * (max_cost+1)
        for i in range(len(costs)):
            C[costs[i]] += 1

        count = 0
        for i in range(1,max_cost+1):
            if C[i] == 0:
                continue

            can_buy = min(C[i], coins // i)

            coins -= can_buy * i
            count += can_buy

            if coins < i:
                break

        return count