Leetcode Python - 1647. Minimum Deletions to Make Character Frequencies Unique

Leetcode #1647 - Minimum Deletions to Make Character Frequencies Unique

이제 두 번째로 100 문제들을 풀어보겠습니다. 리트코드의 문제 1647 ‘Minimum Deletions to Make Character Frequencies Unique’을 파이썬으로 풀어 보도록 하겠습니다.

discuss 참고 포인트는 dictionary 에 저장 후,set으로 해당 숫자가 있으면 -1 해줍니다.

전체 코드는 아래와 같습니다.

class Solution:
    def minDeletions(self, s: str) -> int:
        freq = {}
        for c in s:
            freq[c] = 1 + freq.get(c,0)
        seen = set()
        ans = 0
        for k in freq.values():
            while k in seen:
                k -= 1
                ans += 1
            if k:
                seen.add(k)
        
        return ans

시간복잡도는

• O(n) : O(n) + O(kn) (k는 seen 크기) 최악의 경우 O(n^2) : k가 n일 경우

공간복잡도는

• O(n) : freq(n) + seen(k) (최악의 경우 k = n)