99클럽 코테 스터디 39일차 TIL + [LeetCode] 1338. Reduce Array Size to The Half/힙/JAVA풀이

 

 

 

 

 

 

1. 오늘의 학습 키워드

---

 

 [LeetCode] 1338. Reduce Array Size to The Half/힙/JAVA풀이 자바 

 

 

2. 오늘의 학습 문제 

---

문제

---

 

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

 

You are given an integer array arr. You can choose a set of integers and remove all the occurrences of these integers in the array.

Return the minimum size of the set so that at least half of the integers of the array are removed.

 

Example 1:

Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2
Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).
Possible sets of size 2 are {3,5},{3,2},{5,2}.
Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has a size greater than half of the size of the old array.

Example 2:

Input: arr = [7,7,7,7,7,7]
Output: 1
Explanation: The only possible set you can choose is {7}. This will make the new array empty.

 

Constraints:

• 2 <= arr.length <= 105
• arr.length is even.
• 1 <= arr[i] <= 105

 

 

코드

---

import java.util.*;

/*
1. arr의 각 요소들의 개수를 구하여 맵에 저장
2. 최대힙에 value를 저장
3. 힙에서 poll한 값들의 합이 half보다 작을때까지 반복문수행

*/
class Solution {
    
    static PriorityQueue<Integer> pq ;
    static HashMap <Integer,Integer> map ;
    public int minSetSize(int[] arr) {
        
        int half=arr.length/2;
        
        map=new HashMap<>();
        
        for(int a:arr){ //맵에 arr의 원소:개수 저장
            if(!map.containsKey(a))
                map.put(a,1);
            else{
                map.put(a, map.get(a) +1 ); 
            }
        }
        
        
        
        pq=new PriorityQueue <>(Collections.reverseOrder()); //최대힙
        
        for(int key: map.keySet()){
            pq.add(map.get(key));
        }
        
        int cnt= arr.length;
        int answer=0;
        while(cnt>half){
            cnt-=pq.poll();
            answer++;
        }
        return answer;
        
        
    }
}

 

1. arr에 있는 원소:개수를 맵에 저장한다

2. 맵에 있는 value를 최대힙에 넣는다.

3. cnt를 배열의 크기로 설정, cnt>half일때까지 cnt-=pq.poll()하고 answer++한다.

4. return answer

 

ex)

[3,3,3,3,5,5,5,2,2,7] 의 경우

 

맵에는

 

3:4

5:3

2:2

7:1

이 들어가고, 최대힙에 넣으면

 

   4

 3   2

1

 

꼴이 될 것이다. 

half=5, 

cnt=arr.length=10이므로

cnt>half일때만 cnt-=pq.poll()을 수행하고 answer++하면

삭제해야하는 최소 크기의 원소 셋을 구할 수 있다. 

 

 

3. 오늘의 회고

---

 

• 힙과 해시맵을 이용해 풀었다.
• 해시맵을 스터디 초반에는 사용하기가 좀 어려웠는데, 매일 챌린지 문제를 푸니 익숙하게 사용하게 되는 것 같다. 개인적으로 편리하여 자주 사용하게 된다.