1833. Maximum Ice Cream Bars

조건:

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

의역: 더운 여름 한 남자애가 돈을 가지고 아이스크림 가게로 가서 가지고 있는 돈으로 최대한 많은 아이스크림을 사려고 할때 남자애가 구매할 수 있는 최대 아이스크림 갯수를 반환하시오 

아이스크림들의 가격 정보: 길이 n의 정수형 배열 costs

남자아이가 가지고 있는 돈의 액수 정보: coins 

의역:

예시 1에서 남자애가 7 coins 을 가지고 최대한 많은 수의 아이스크림을 구매할 수 있는 경우의 수는 1 + 3 + 2 + 1 = 7 임으로 4를 반환

예시 2에서 남자애가 5 coins 을 가지고 살 수 있는 아이스크림은 없기 때문에 0을 반환

예시 3에서 남자애가 20 coins 을 가지고 모든 아이스크림을 사는게 가능하기 때문에 배열의 길이수 6을 반환 

 

풀이:

1. 정렬 기능 이용 

class Solution {
    public int maxIceCream(int[] costs, int coins) {
        // 시간 복잡도 O(nlog n) 공간 복잡도 O(nlog n) - sort 함수 때문에
        Arrays.sort(costs);
        int ans = 0;
        for (int price: costs) {
            if(coins-price<0)
                break;
            coins-=price;
            ans++;
        }
        return ans;
    }
}

1-1: 배열의 요소 범위가 크지 않다는 점을 이용해 계수 정렬 사용 (리츠코드 공식 풀이) 

class Solution {
	// 시간 복잡도 O(2n+m) 공간 복잡도 O(m)
    public int maxIceCream(int[] costs, int coins) {
        int ans = 0;
        int max = costs[0];
        for (int cost:costs) {
            if(max<=cost)
                max = cost;
        }
        // 아이스크림 제일 비싼 가격+1 만큼의 배열을 만듬
        int iceCreamNumArray[] = new int[max+1];
        for (int cost:costs) {
            iceCreamNumArray[cost]++;
        }
        for(int i=1;i<iceCreamNumArray.length;i++){
            if(iceCreamNumArray[i]==0)
                continue;
            if(coins<i)
                break;
            // 남아 있는 코인의 수가 해당 아이스크림 가격의 아이스크림 전부를 구매 못 하는 경우
            // 가능한 갯수만 구매 하도록 
            int count = Math.min(iceCreamNumArray[i],coins/i);
            coins -= i * count;
            ans+=count;
        }
        return ans;
    }
}

 

링크: https://leetcode.com/problems/maximum-ice-cream-bars/description/

 

메모: 배열의 요소 범위가 크지 않다면 계수 정렬을 쓰자!