문제

1481. Least Number of Unique Integers after K Removals

User Accepted:6285
User Tried:6983
Total Accepted:6437
Total Submissions:12682
Difficulty:Medium

Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.

Example 1:
  Input: nums = [10,9,2,5,3,7,101,18]
  Output: 4
  Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:
  Input: nums = [0,1,0,3,2,3]
  Output: 4
  
Example 3:
  Input: nums = [7,7,7,7,7,7,7]
  Output: 1
 

Constraints:
  1 <= nums.length <= 2500
  -104 <= nums[i] <= 104

풀이

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        # arr = [5, 5, 4], k = 1
        elem_count ={}
        
        for num in arr:
            if num in elem_count:
                elem_count[num] += 1
            else:
                elem_count[num] = 1
        # print(elem_count) {5: 2, 4: 1}
        
        #dictionary의 value만으로 이루어진 list를 만든다.
        counter_list = list(elem_count.values())
        # print(counter_list) [2, 1]
        counter_list.sort()
        answer = len(counter_list)
        
        for count in counter_list:
            if k >= count:
                k -= count
                answer -= 1
            else:
                break

        return answer

dictionary 구조를 이용하여 각 원소와 개수를 연결시킨 후, 원소의 개수만으로 이루어진 list를 만들어서 반복문과 k를 이용하여 답을 구하는 방식으로 풀었다.
배열(혹은 list)은 자주 써봐서 익숙하지만 아직까지도 dictionary(또는 hash table)를 문제 풀이 과정 중에 떠올리는 게 좀 어색하다. 그리고 dictionary의 value를 이용하여 list를 만드는 것도 좀 생소했었다.