[Leetcode 1338] Reduce Array Size to The Half - 그리디 알고리즘

오늘의 학습 키워드

그리디 알고리즘

---

알고리즘 문제

LeetCode Medium - 1338. Reduce Array Size to The Half

---

공부한 내용

그리디 알고리즘

• 최적해를 구하는 알고리즘
• 전체 최적해를 구하기 위해 각 단계에서 최선의 선택을 한다.
• 문제를 해결하는 과정에서 현재 상황에서의 최적의 해법을 찾는 과정을 반복하며 최종 해답을 도출한다.

---

오늘의 회고

처음 시도

• 완전 탐색을 해야해서 DFS를 사용해야 하나 생각했다. 
  • 문제1. 배열 최대 크기가 10^5인데, 모두 탐색하면 2^10^5 = 1,125,899,906,842,624 번을 탐색해야 한다.
  • 문제2. DFS로 최적의 해를 찾더라도, 다시 돌아와서 다른 경로를 탐색하면 최적의 해를 놓칠 수 있다.

해결

• 그리디 알고리즘으로 가장 빈도수가 많은 숫자부터 주어진 배열의 전체 길이의 반이 될때까지 빈도수를 더해서 답을 구할 수 있다.

---

문제 풀이

import java.util.*;

class Solution {
    public int minSetSize(int[] arr) {
        int len = arr.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : arr) {
            map.put(n, map.getOrDefault(n, 0)+1);
        }
        List<Integer> values = new ArrayList<>(map.values());
        Collections.sort(values);

        int res = 0, sum = 0;
        for (int i = values.size()-1; i >= 0; i--) {
            sum += values.get(i);
            res++;

            if (sum >= Math.round(len/2)) break;
        }

        return res;
    }