프로그래머스 귤고르기 java

문제링크

문제 접근

• 각 사이즈인 갯수가 몇개인지 체크 -> 정렬하여 많은 것부터 담기

코드

import java.util.*;
class Solution {
    public int solution(int k, int[] tangerine) {
        int answer = 0;
        int len = tangerine.length;
        // 첫번 째 풀이, 낭비되는 배열 및 정렬 시간 증가
        // int[] countArray = new int[10000001];
        // for(int i=0;i<len;i++){
        //     countArray[tangerine[i]]++;
        // }
        // Arrays.sort(countArray);
        // for(int i=10000001-1;i>=1;i--){
        //     k -= countArray[i];
        //     answer++;
        //     if(k <= 0) break;
        // }
        
        // 두번째 풀이 Map 사용하여 존재하는 사이즈만 계산
        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0;i<len;i++){
            map.put(tangerine[i], map.getOrDefault(tangerine[i],0)+1);
        }
        List<Integer> list = new ArrayList<>(map.values());
        Collections.sort(list);
        for(int i=list.size()-1;i>=0;i--){
            k -= list.get(i);
            answer++;
            if(k <= 0) break;
        }
        
        return answer;
    }
}

결과

• 1번 풀이
  

• 2번 풀이
  

정리

• 결국 사이즈의 범위가 1~10000000까지 있다면 시간 비슷
• 하지만 사이즈의 범위가 작다면 2번 풀이가 효율적
• 자료구조를 활용한 풀이 접근하자