99클럽 코테 스터디 39일차 TIL + Heap(Reduce Array Size to The Half)

오늘의 과제

리트코드 medium으로 분류된 Reduce Array Size to The Half 입니다.

 

이번 유형은 힙 입니다.

문제

https://leetcode.com/problems/reduce-array-size-to-the-half/description/

 

먼저 문제 요구사항 요약입니다.

 

배열이 주어질 때 크기를 절반 이하로 줄이기 위해 제거해야 할 최소 요소 수를 반환하는 문제입니다.

 

요소를 최소한으로 줄이기 위해 가장 많이 중복되는 요소를 먼저 찾습니다.

// 빈도수 계산
Map<Integer, Integer> freqMap = new HashMap<>();
for (int num : arr) {
    freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}

 

문제의 예시인 {3, 3, 3, 3, 5, 5, 5, 2, 2, 7}의 배열로 본다면 빈도수는 다음과 같습니다

 

3: 4개 (key : 3, value : 4)

5: 3개 (key : 5, value : 3)

2: 2개 (key : 2, value : 2)

7: 1개 (key : 7, value : 1)

 

freqMap에는 순서가 없이 값들이 들어있으니 가장 많이 중복되는 요소를 선별하여 제거하기 위해 Collections.sort를 통해 내림차순으로 정렬합니다.

// 빈도수 정렬
List<Integer> freqList = new ArrayList<>(freqMap.values());
Collections.sort(freqList, Collections.reverseOrder());

 

이제 배열을 절반 이하로 줄이기 위해 내림차순으로 정렬된 요소들을 제거합니다. 정렬된 순서대로 4개가 있는 3을 제거, 3개가 있는 5를 제거하면 총 7개를 제거하기 때문에 배열의 크기는 절반 이하로 줄어듭니다.

// 빈도가 높은 요소부터 제거
int count = 0;
int removedElements = 0;
int halfSize = arr.length / 2;
for (int freq : freqList) {
    removedElements += freq;
    count++;
    if (removedElements >= halfSize) {
        break;
    }
}

 

 

 

코드입니다.

import java.util.*;

public class Solution {
    public int minSetSize(int[] arr) {
        // 빈도수 계산
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : arr) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        // 빈도수 정렬
        List<Integer> freqList = new ArrayList<>(freqMap.values());
        Collections.sort(freqList, Collections.reverseOrder());

        // 빈도가 높은 요소부터 제거
        int count = 0;
        int removedElements = 0;
        int halfSize = arr.length / 2;
        for (int freq : freqList) {
            removedElements += freq;
            count++;
            if (removedElements >= halfSize) {
                break;
            }
        }

        return count;
    }
}

 

배운 점

리드코드에서 제공하는 힌트를 보지 않겠다 다짐했으나 결국 힌트에서 풀이 방법을 얻어냈습니다. 그래도 이젠 문제를 보고 어떤걸 요구하는지 빠르게 캐치할 수 있을지 알았는데 리트코드는 사실 뭘 원하는지 찾아내기가 아직까진 힘이 듭니다. 문해력의 부족인건지, 단순히 문제 경험이 적은건지 아직은 모르겠으나 꾸준히 풀다보면 뭔가 해결되지 않을까 싶습니다.

 

 

오늘의 한줄평

주변을 보고 조급해 하지 말자. 그저 내 걸음 속도대로 멈추지 않고 꾸준히 가면 된다.