귤 고르기

문제

경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 귤의 크기가 일정하지 않아 보기 좋게 상자를 포장하기 위해, 상자에 담기는 귤의 크기 종류가 최소가 되도록 고르려고 합니다. 경화가 한 상자에 담으려는 귤의 개수 k와 귤의 크기를 담은 배열 tangerine이 매개변수로 주어집니다. 귤 k개를 고를 때 크기 종류의 최솟값을 반환하는 프로그램을 작성하는 문제입니다.

• 입력: 한 상자에 담으려는 귤의 개수 k (1 ≤ k ≤ 100,000), 귤의 크기를 담은 배열 tangerine (길이 1 이상 100,000 이하, 귤의 크기는 1 이상 10,000,000 이하)
• 출력: 상자에 담긴 귤 크기의 서로 다른 종류 수의 최솟값

링크: https://school.programmers.co.kr/learn/courses/30/lessons/138476

풀이 1: 카운팅 배열을 활용한 정렬

귤의 크기가 최대 10,000,000이므로, 크기가 천만인 정수 배열을 만들어 각 귤의 등장 횟수를 세고, 이를 리스트에 옮겨 담아 많은 순서대로(내림차순) 담는 가장 직관적인 방식입니다.

• 빈도수 카운팅: 10,000,001 크기의 배열 cnt를 선언하고 한 번 순회하며 개수를 증가시킵니다.
• 유효 개수 추출: 빈도수가 0이 아닌 값들만 리스트에 담습니다.
• 내림차순 정렬 및 탐욕법: 리스트를 내림차순 정렬한 뒤, 필요한 귤의 개수 k에서 차감해 나가며 종류 수를 셉니다.

코드 1

import java.util.*;

class Solution {
    public int solution(int k, int[] tangerine) {
        // 1. 크기별 귤의 개수를 저장할 카운팅 배열 선언
        int[] cnt = new int[10000001];
        for (int t : tangerine) {
            cnt[t]++;
        }
        
        // 2. 1개 이상 존재하는 귤의 '개수'만 리스트에 수집
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= 10000000; i++) {
            if (cnt[i] != 0)
                list.add(cnt[i]);
        }
        
        // 3. 개수가 많은 순서대로 처리하기 위해 내림차순 정렬
        Collections.sort(list, Collections.reverseOrder());
        
        int idx = 0, ans = 0;
        // 4. 필요한 개수(k)를 채울 때까지 가장 개수가 많은 종류부터 담기
        while(k > 0) {
            k -= list.get(idx);
            idx++;
            ans++;
        }
        
        return ans;        
    }
}

풀이 2: 원본 배열 정렬을 활용한 메모리 최적화 풀이

• 배열 정렬: Arrays.sort(tangerine)을 통해 귤들을 크기순으로 나열합니다. 크기가 같은 귤들은 서로 인접하게 배치됩니다.
• 연속된 요소 카운팅: 정렬된 배열을 한 번만 순회하며, 바로 앞의 귤과 크기가 같다면 카운트를 증가시키고, 다르면 지금까지 센 카운트를 리스트에 저장합니다.
• 공간 복잡도를 크게 줄이면서 시간 복잡도는 O(N log N)으로 매우 준수하게 동작합니다.

코드 2

import java.util.*;

class Solution {
    public int solution(int k, int[] tangerine) {
        // 1. 귤의 크기를 기준으로 오름차순 정렬
        Arrays.sort(tangerine);
        
        List<Integer> counts = new ArrayList<>();
        int currentCount = 1;
        
        // 2. 정렬된 배열을 순회하며 연속된 같은 크기의 귤 개수 세기
        for (int i = 1; i < tangerine.length; i++) {
            if (tangerine[i] == tangerine[i - 1]) {
                currentCount++;
            } else {
                counts.add(currentCount); // 크기가 달라지면 개수 저장
                currentCount = 1;         // 카운트 초기화
            }
        }
        counts.add(currentCount); // 마지막 그룹 추가
        
        // 3. 개수를 기준으로 내림차순 정렬
        Collections.sort(counts, Collections.reverseOrder());
        
        int ans = 0;
        // 4. 탐욕법으로 가장 개수가 많은 귤부터 상자에 담기
        for (int count : counts) {
            if (k <= 0) break;
            k -= count;
            ans++;
        }
        
        return ans;
    }
}

알고리즘 분류

탐욕법 (Greedy), 정렬 (Sorting), 해시 (Hash) / 카운팅 배열