[프로그래머스] 귤 고르기

 

import java.util.*;

class Solution {
    public int solution(int k, int[] tangerine) {
        int answer = 0; // 크기 다른 서로 다른 종류 수
        Arrays.sort(tangerine);
        int length = tangerine[tangerine.length-1]+1;
        int[] arr = new int[length]; // 각각 귤 몇개인지 
        // i크기의 귤은 arr[i]개수만큼 있다 
        
        for(int i = 0; i < tangerine.length; i++){
            for(int j = 1; j < arr.length; j++){
                if(j == tangerine[i]){
                    arr[j]++;
                }
            }
        }
        
        Arrays.sort(arr); // 오름차순으로 정렬
        for(int i = arr.length-1; i >= 0; i--){
            if(k <= 0) break;
            k -= arr[i];
            answer++;

        }
        
//        System.out.println(Arrays.toString(arr));
        
        return answer;
    }
    /*
    public static void main(String[] args){
        Solution sol = new Solution();
        int[] tangerine = {1, 3, 2, 5, 4, 5, 2, 3};
        int answer = sol.solution(6, tangerine);
        
    }
    */
}

정확성: 76.5

합계: 76.5 / 100.0

시간초과,,,,,,,,,

 

import java.util.*;

class Solution {
    public int solution(int k, int[] tangerine) {
        int answer = 0; // 크기 다른 종류의 수
        Arrays.sort(tangerine);
        int cnt = 0;
//        System.out.println(Arrays.toString(tangerine));
        
        ArrayList<Integer> list = new ArrayList<>(); // 귤 몇 개 담겨있는지
        
        for (int i = 0; i < tangerine.length; i++) {
            cnt++;
            
            if ((i < tangerine.length - 1 && tangerine[i] != tangerine[i+1])
                || (i == tangerine.length - 1 && cnt > 0)) {
                
                list.add(cnt);
                cnt = 0;
            }
        }
//       System.out.println(list);
        
        Collections.sort(list, Collections.reverseOrder());
        
        for (int i : list) {
            answer++;
            k -= i;
            
            if (k <= 0) {
                break;
            }
        }
        
        return answer;
    }
    
}