1481. Least Number of Unique Integers after K Removals

[zeikar]

Problem link

https://leetcode.com/problems/least-number-of-unique-integers-after-k-removals

Problem Summary

배열의 수들을 k개 삭제했을 때 unique한 수의 최소 개수를 구하는 문제.

Solution

그리디로 풀면 된다. 갯수가 적은 수부터 삭제하면 unique한 수를 최소한으로 줄일 수 있다.
map으로 개수를 세고 개수를 기준으로 정렬한 뒤 앞에서부터 제거하면 된다.

O(n)

에디토리얼 보니 O(n)으로도 되는데 정렬하지 않고 나온 개수를 다시 맵에 넣는 방식으로 하면 O(n)이 가능하다. (Counting Sort)
나온 개수를 맵에 넣은 뒤 1부터 체크해서 차례로 제거하면 된다.

Source Code

O(n log n)

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        cnt = defaultdict(int)
        for num in arr:
            cnt[num] += 1
        
        removed = 0
        for (_, v) in sorted(cnt.items(), key=lambda item: item[1]):
            if k == 0:                
                return len(cnt) - removed
            if k < v:
                return len(cnt) - removed
            k -= v
            removed += 1
        return 0

O(n)

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        cnt = defaultdict(int)
        for num in arr:
            cnt[num] += 1
        
        freq = defaultdict(int)
        for f in cnt.values():
            freq[f] += 1
        
        removed = 0
        for f in range(1, len(arr) + 1):
            n = freq[f]

            if n == 0:
                continue

            if k >= f * n:
                k -= f * n
                removed += n
            else:
                c = (k // f)
                k -= c * f
                removed += c

            if k <= 0:
                break

        return len(cnt) - removed