99클럽 코테 스터디 39일자 TIL + reduce-array-size-to-the-half

문제 출처

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

학습 키워드

힙, 인데 해시맵으로 풀었다.

시도 방법

풀이전략
1. arr개수를 저장한다.
2. 해시맵으로 key-value 방식으로 개수를 저장한다.
3. 해시맵을 정렬처리한다. (value 가 가장 큰 순서대로)
4. 개수를 제거하면서 arr의 1/2 가 되는 시점의 count값을 리턴한다.

내가 작성한 코드

class Solution {
    public int minSetSize(int[] arr) {
        
        int arrSize = arr.length; 
        int halfSize = arr.length; 

        HashMap<Integer , Integer> map = new HashMap<>(); 

        for(int num : arr) {
            map.put(num , map.getOrDefault(num , 0) + 1);
        }

        //value 기준으로 정렬
        ArrayList<Map.Entry<Integer , Integer>> list = new ArrayList<>(map.entrySet()); 
        list.sort((entry1 , entry2) -> entry2.getValue().compareTo(entry1.getValue()));

        int count = 0 ; 
        while(arrSize/2 < halfSize ) {
            
            halfSize -= list.get(count).getValue(); 
            count++; 

        }

        return count; 
    }
}

코드설명

이 문제의 포인트는 현재 arr의 크기를 절반으로 줄일 수 있는 값의 최소 개수를 구하는 것이다. 따라서 그리디 방식으로 가장 값의 빈도가 많은 경우를 찾아 사이즈를 줄여가면서 arr의 사이즈가 1/2 이하로 되는 순간 count를 출력했다.

예시 데이터 )
[3,3,3,3,5,5,5,2,2,7]

이를 해시맵으로 처리하면
[3 : 4 , 5 : 3 , 2 : 2 , 7 : 1 ] 이 되고 value 기준 역순 처리했다.

while(arrSize/2 < halfSize ) {            
    halfSize -= list.get(count).getValue(); 
    count++; 
}

에서 count = 0 일때 4가 출력되어 halfSize에서 차감을 한다.
그럼 arrSize는 10 이고 halfSize 는 6이므로 아직 1/2 가 되지 않았다.

count = 1 일때 3이 출력되어 halfSize에서 차감을 한다.
그럼 arrSize는 10이고 halfSize는 3이므로 1/2 이하가 되어

count 추가후 리턴을 했다.

출력결과

새롭게 알게된 점

새로 알게 된 건 아니지만 복습차원에서 한번 더 작성

(1) getOrDefault 로 맵의 값을 편하게 처리하기

이전코드) 

if(map.get(key) == null) { 
	map.put(key , 1); 
} else {
	map.put(key , map.get(key) + 1 ); 
}

개선된 코드) 

map.put(key , map.getOrDefault(key , 0) + 1 ) ; 

(2) map의 value를 기준으로 정렬하기

ArrayList<Map.Entry<Integer, Integer> list = new ArrayList<>(map.entrySet()); 

list.sort((entry1 , entry2) -> entry2.getValue().compareTo(entry1.getValue())); 

다음에 풀어볼 문제 - optimal-partition-of-string

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL