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

       문제 요약        

- 문제

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

프로그래머스

 

 

         아이디어        

 

1. map 자료구조를 이용해서, 수확한 귤의 종류별 개수를 구한다

2. 제거해야 하는 개수만큼 제거한다

단, 종류별 개수를 오름차순 정렬하여 제거함으로써 최대한 많은 종류를 없애도록 한다 

         소스코드        

 

import java.util.*;
class Solution {
    static Map<Integer, Integer> map;
    public int solution(int k, int[] tangerine) { // k 고를 귤의 수 
        int answer = 0;
        map = new HashMap<>();
        for(int t = 0; t < tangerine.length; t++) {
            int x = tangerine[t];
            map.put(x, map.getOrDefault(x, 0) + 1);
        }
        List<Integer> values = new ArrayList<>(map.values());
        Collections.sort(values);
        
        int all = 0; // 모든 귤의 수
        for(int i = 0; i < values.size(); i++) {
            all += values.get(i);
        }
        
        int needRemoved = all - k; 
        int removedIdx = -1;
        int removed = 0;
        for(int removeI = 0; removeI < values.size(); removeI++) {
            if (removed + values.get(removeI) <= needRemoved){
                removed += values.get(removeI);
                removedIdx = removeI;
                continue;
            } else {
                break;
            }
        }

        answer = values.size() - (removedIdx + 1); 
        
        return answer;
    }

}