Reduce Array Size to The Half [LeetCode]

문제 풀이 정리

 

Given an 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 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.

Example 3:

Input: arr = [1,9] Output: 1

Example 4:

Input: arr = [1000,1000,3,7] Output: 1

Example 5:

Input: arr = [1,2,3,4,5,6,7,8,9,10] Output: 5

 

Constraints:

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

코드

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        
        num_dict = {}
        arr_len = len(arr)
        for num in arr:
            if num in num_dict:
                num_dict[num]+=1
            else:
                num_dict[num] = 1
                
        num_dict = sorted(num_dict.items(), key = lambda x : x[1], reverse=True)
        
        add_set = set()
        count_sum = 0
        for num, count in num_dict:
            if count_sum < arr_len/2:
                add_set.add(num)
                count_sum += count
            else:
                break
                
        answer = len(add_set)
        return answer

 

문제 넋두리

어려운 문제는 아니였지만, 역시 영어가 문제다

구글 번역 돌려서 이해해야되고,,,,

 

배열에서 숫자들 빼면서 배열의 길이가 처음보다 반토막 이상 짧아지면 break하게 풀었다.

리트코드는 편한게 안돌아가는 테스트 케이스를 볼 수 있어서 내 로직에 어디가 문제인지 빨리 알수있다.