문제

문제링크
난이도: Level 2
알고리즘 분류: 그리디, 정렬

틀린 코드

조합으로 뽑고 HashSet에 담아서 사이즈로 최솟값을 구하려고 함 (완전탐색)

2/3가 시간초과 난다.

import java.util.*;

class Solution {
    static int answer;
    
    public int solution(int k, int[] tangerine) {
       
        answer = tangerine.length;
        comb(tangerine, new int[k], 0, 0);
        
        return answer;
    }
    
    public void comb(int[] origin, int[] selected, int selectedIdx, int originIdx) {
        if(selected.length == selectedIdx) {
            Set<Integer> pick = new HashSet<>();
            for(int i=0; i<selectedIdx; i++) {
                pick.add(selected[i]);
            }
            answer = Math.min(answer, pick.size());
            return;
        }
        
        for(int i=originIdx; i<origin.length; i++) {
            selected[selectedIdx] = origin[i];
            comb(origin, selected, selectedIdx+1, i+1);
        }
        
    }
}

틀린 코드2

정렬한 후 누적합을 통해 하나씩 크기를 비교하려 했는데 생각해보니 풀이 자체에 오류가 있었다.

통과 코드

정렬, 그리디

크기별 개수를 저장하는 배열을 만들고 정렬한 후, 가장 개수가 많은 배열 마지막부터 더하면서 k가 넘을 때 선택한 귤의 개수를 출력한다.

import java.util.*;

class Solution {
    public int solution(int k, int[] tangerine) {
        int answer = 0;
        Arrays.sort(tangerine);
        int[] tanBySize = new int[tangerine[tangerine.length-1]+1];
        for(int i=0; i<tangerine.length; i++) {
            tanBySize[tangerine[i]]++;
        }
        Arrays.sort(tanBySize);
        int sum=0;
        for(int i=tanBySize.length-1; i>0; i--) {
            sum += tanBySize[i];
            if(sum >= k) {
                answer=tanBySize.length-i;
                break;
            }
        }
        
        return answer;
    }
}

결과

총평

문제 풀다가 sum이 k개만 넘으면 되는건데 sum == k 일때만 통과할 수 있다고 생각이 꼬여서 오래걸림.
문제가 계속 안풀리면 문제 다시 읽고 지금 생각한 로직이 맞는지 점검하자.