[LeetCode] 1338. Reduce Array Size to The Half

- Problem

1338. 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 <= 10^5
• arr.length is even.
• 1 <= arr[i] <= 10^5

주어진 배열 arr의 길이를 반 이하로 만들 수 있는 집합의 최소 크기를 반환하는 문제이다.
즉, 예제 1에서 arr에서 3을 선택한다면 배열의 모든 3을 지운 [5,5,5,2,2,7]이 되는 것이다.
예제 1에서 arr의 길이를 반 이하로 줄일 수 있는 정수의 집합은 {3,7}, {3,5},{3,2},{5,2} 이 있고, 최소 길이 집합은 2이다.

- 내 풀이

접근법은 다음과 같다.

1. 주어진 배열의 길이array_length와 타겟 길이(목표로 하는 배열의 길이)target_length를 정의한다.
2. counter 모듈을 이용하여 정수별로 빈도수를 구한다.
3. 키 값은 필요 없으니 밸류 값만 오름차순으로 정렬하여 배열로 정의한다.
4. array_length에서 frequency를 pop하며 뒤에 값부터 빼준다. (큰 값부터) 연산마다 answer를 1씩 증가시켜준다.
   • 이때 answer의 수는 제거한 정수의 개수가 되는 셈

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        array_length = len(arr)
        target_length = array_length // 2
        answer = 0
        
        counter_array = collections.Counter(arr)
        frequency = sorted(counter_array.values())
        
        while array_length > target_length:
            array_length -= frequency.pop()
            answer += 1
                
        return answer

- 결과

음?