[LeetCode] 1338 | Reduce Array size to The Half | Python

---

문제 링크: 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.

---

조건

• 2 <= arr.length <= $10^5$
• arr.length is even.
• 1 <= arr[i] <= $10^5$

---

내 풀이

arr안의 원소의 개수를 nums라는 dict안에 저장한다.

nums를 value값으로 내림차순으로 정렬한 뒤, 가장 큰 value부터 뽑아서 누적시킨다.

누적시킨 값이 len(arr)/2보다 커지면 그때까지의 수를 리턴한다.

---

코드

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        N = len(arr)
        nums = defaultdict(int)
        
        for num in arr:
            nums[num] += 1
        
        nums = sorted(nums.items(), key = lambda x: x[1], reverse=True)
        
        count = 0
        ans = 0
        for key, value in nums:
            count += value
            ans += 1
            if count >= N/2:
                return ans