[코테연습] 1338. Reduce Array Size to The Half

- 힙 문제
- 문제 분석
 1. arr 에 들어있는 숫자를 제거한다.
 2. 중복된 숫자는 함께 제거 된다. ( ex) [3,3,3,3,5,5,5,2,2,7] : 3 제거 => [5,5,5,2,2,7] )
 3. 기존 arr 의 length 의 절반이 되도록 숫자를 가장 최소한으로 제거해라.
 4. 이때 가장 최소한의 숫자를 return
 
- 문제 풀이

    1. for 문을 1번 돌려 중복 된 Integer 의 숫자를 센다.
    2. 센 숫자를 map 으로 저장한다. key = 숫자 value = counting
    3. List<List>> graph 를 선언한다.
    4. new ArrayList() 로 초기화
    5. map 을 for 문으로 돌리면서 graph.get(value).add(key) 로하여 counting 한것으로 숫자를 graph 에 저장한다.
    6. graph 를 역순으로 반복문 for 로 돌린다.
    -> 이 경우 가장 많은 수가 맨 마지막에 저장
    7. 총 arr.length 값의 절반인지 여부를 확인하면서 counting

 

 

class Solution {
    public int minSetSize(int[] arr) {
           
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < arr.length; i++) {
            int num = arr[i];
            map.put(num, map.getOrDefault(num, 0)+1);
        }

        int n = arr.length;
        List<List<Integer>> graph = new ArrayList<>();

        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        for(int key: map.keySet()) {
            int value = map.get(key);
            graph.get(value).add(key);
        }

        int cnt = 0;
        int totalSize = arr.length;
        boolean finish = false;
        for(int i = graph.size()-1; i >= 0; i--) {
            List<Integer> g = graph.get(i);
            if (finish) break;

            if (!g.isEmpty()) {
                for (int j = 0; j < g.size(); j++) {
                    int len = i;
                    totalSize-=len;
                    cnt++;
                    if (totalSize < n/2+1) {
                        finish = true;
                        break;
                    } 
                }
            }

        }
        return cnt;
    }
}