99클럽 코테 스터디 30일차 TIL [LeetCode] Reduce Array Size to The Half (Java)

📃 문제

[LeetCode] Reduce Array Size to The Half

🖋️ 풀이

• 주어진 배열 arr를 이루는 각 요소의 빈도를 계산해 frequencyMap에 저장한다.
• 최대힙 maxHeap에 해시맵의 값들(빈도)를 저장한다.
  • 최대힙 구현을 위해 내림차순 정렬을 정의
• 빈도가 가장 높은 요소를 제거하고, 그 값만큼 removedElements에 더한다.
• 제거된 요소의 개수가 주어진 배열 크기의 절반 이상이 될 때까지 반복한다.
• 제거된 집합의 크기 setSize를 반환한다.

✅ 정답 코드

class Solution {
    public int minSetSize(int[] arr) {
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : arr) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }
        
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int frequency : frequencyMap.values()) {
            maxHeap.add(frequency);
        }

        int removedElements = 0;
        int setSize = 0;
        int halfSize = arr.length / 2;

        while (removedElements < halfSize) {
            removedElements += maxHeap.poll();
            setSize++;
        }
        
        return setSize;
    }
}

🔍 다른 풀이

• 주어진 배열을 순회하며 최댓값을 구해 max에 저장한다.
• 각 요소 num을 인덱스로 배열 freq에 빈도를 카운트한다.
• 빈도 배열을 정렬한다.
• 배열 크기가 절반이 될 때까지 빈도가 가장 큰 수부터 제거하는 작업을 반복한다.
• 제거된 수의 개수 count를 반환한다.

class Solution {
    public int minSetSize(int[] arr) {
        int max = Integer.MIN_VALUE;
        for(int num : arr){
            max = Math.max(max, num);
        }

        int freq[] = new int[max+1];
        for(int num : arr){
            freq[num]++;
        }
        Arrays.sort(freq);

        int i = max;
        int n = arr.length;
        int count = 0;
        while(n > arr.length / 2){
            n = n - freq[i];
            i--;
            count++;
        }
        
        return count;
    }
}

• 기존 풀이와의 비교 결과
  빈도 배열을 사용한 풀이가 최대힙을 사용한 코드보다 더 효율적인 시간 복잡도와 공간 복잡도를 가짐