[JAVA] 귤 고르기

< 내 풀이 > 

import java.util.*;
class Solution {
    public int solution(int k, int[] tangerine) {
        int answer = 0;
        int arr[]=new int[10000001];
        
        for(int i=0;i<tangerine.length;i++){
            arr[tangerine[i]]++; // arr[귤 크기] 의 값 증가 
        }
       
        Arrays.sort(arr); // 배열 오름차순 정렬
        
        int index=arr.length-1; // 맨 뒤의 값에 접근하기 위함 (가장 값이 크다 => 해당 크기의 귤이 많다)
        while(k>0){
            k=k-arr[index]; //  k에서 해당 index의 귤의 개수를 뺀다. 
            index--; 
            answer++; // 귤의 종류 수 증가 
        }
        return answer;
    }
}

 

✏️ 풀이 방법

 

서로 다른 종류의 수가 최소가 되려면, 중복이 많이 되는 크기의 귤을 우선적으로 골라야한다. 

ex) k=2, tangerine={1,1,1,1,2,2,2,3} 일 때

arr [1] = 4, arr [2] =3, arr [3] =1 이 되고, 오름차순 정렬 후에는 arr 배열의 상태가 {... 1, 3, 4 } 가 된다.

위의 코드대로 반복문을 실행하면 첫 번째 반복에서 k= -2 가 되고 귤의 종류 수는 1이 된 채로 반복문이 종료된다.

 

< 다른 사람의 풀이 >

import java.util.*;

class Solution {
    public int solution(int k, int[] tangerine) {
        int answer = 0;
        HashMap<Integer,Integer> map =new HashMap<>();

        for (int t : tangerine) {
            map.put(t, map.getOrDefault(t, 0) + 1);
        }

        List<Integer> list = new ArrayList<>(map.keySet());
        list.sort((o1, o2) -> map.get(o2)-map.get(o1));

        for(Integer key:list){
            k -=map.get(key);
            answer++;
            if(k<=0){
                break;
            }
        }

        return answer;
    }
}

 

✍🏻 느낀점

 

 뭔가 내 풀이가 좋은 것 같지는 않다. int arr[]=new int[10000001]; 로 배열의 크기를 선언해놨기 때문에 실질적으로 메모리를 너무 낭비하고 있지 않나하는 생각이 든다. 저번에 해시맵 관련 문제를 풀어봤는데, 뭔가 제대로 써본 적이 없어서 이런 문제를 봤을 때 해시맵이 바로 떠오르지 않는다. 안 써 봤다고 그냥 모르는 채로 두지 말고, 문제에 적용할 수 있을 정도로 익숙해져야겠다💪🏻