Minimum Deletions to Make Character Frequencies Unique

어떤 문자열 s의 모든 글자가 모두 다른 빈도로 나타나면 좋다고 정의하자.

문자열이 주어졌을 때, 이 문자열을 좋게 만들기 위해서 삭제해야하는 글자의 최소 개수를 구하자.

문자열에서 글자의 빈도란 문자열에서 글자가 나타나는 횟수를 뜻한다. 예를 들어 "aab"에서 a의 빈도는 2이고 b의 빈도는 1이다. 모든 글자의 빈도가 다르므로 이 문자열은 좋다.

문자열의 길이는 1 ~ 100,000 사이이고 알파벳 소문자만 포함한다. 빈도가 0인 글자, 즉 문자열에 등장하지 않는 글자는 문자열의 좋음과 상관없다.

중복이 없어질 때까지 빼기

일단 문자열에서 글자의 빈도를 세는 것은 쉽다. 그 다음이 문제다. 빈도를 기준으로 중복을 찾아서, 중복이 없을 때까지 각각의 글자를 하나 씩 빼야한다. 글자가 두 개만 중복이면 쉽게 하겠지만 그런 조건이 없으므로, 실제로 중복되는 글자는 알파벳 소문자 수 만큼인 최대 26개가 가능할 것이다. 그렇다고 26개를 일일이 처리하는 것은 바보같은 짓이다. 뭔가 좀더 똑똑한 방법이 있을 것이다.

일단 빈도를 셌으면 사실 그게 무슨 글자인지는 더 이상 알 필요가 없다. 빈도 값만 겹치지 않게 빼면서 유니크한 빈도 집합을 만들면 된다. 빈도를 쭉 훑으면서 이전에 나온 빈도를 기록해둔다고 하자. 그러면 어느 시점에서 이전에 나온 빈도와 같은 부분을 찾게 된다. 그 다음은? 빈도가 같은게 없을 때까지 계속 1씩 빼는 수밖에 없다. 그렇게 빼서 이전에 나온 빈도와 겹치지 않는 빈도 값을 찾았다면, 그 빈도를 빈도 집합에 넣으면 된다.

이때 한 가지 예외는 바로 빈도가 0이 되는 경우다. 빈도가 0이면 문자열의 좋고 나쁨에 영향을 주지 않기 때문에 더 이상 뺄 필요가 없다.

이 아이디어를 구현해보자.

def minDeletions(s):
    deleted = 0
    seen_freq = set()
    for freq in Counter(s).values():
        while freq > 0 and freq in seen_freq:
            freq -= 1
            deleted += 1
        seen_freq.add(freq)
    return deleted

시간 복잡도는 어떻게 될까? 문자열의 길이를 N, 가능한 최대의 글자 개수를 K라고 하면 (1 <= K <= 26), O(N + K^2)이 된다. 일단 빈도를 세는데 (Counter(s)) O(N)이 소요되고, 그 다음 각각의 빈도 값에 대해서 중복이 없을 때까지 1씩 빼야하는데, 최악의 경우 모든 글자가 전부 같은 빈도 값이면 빈도 전체에 대해서 2중 반복문을 도는 것과 마찬가지 이므로 K^2이 된다. 따라서 O(N + K^2)이다. 공간 복잡도는 빈도 기록을 위한 해시 셋만 필요하므로 O(K)이다.

가장 큰 중복부터 제거하기

중복을 제거하는 방법 중에 재밌는게 많아서, 여러가지를 보다가 이해하기 쉽고 괜찮은 것을 하나 더 가져왔다. 바로 힙을 이용하는 것이다.

일단 빈도를 세서 값만 유지하는 것은 이전의 해시셋 접근과 같다. 여기서는 셋을 유지하지 않고 곧바로 이 빈도 목록을 최대 힙으로 만들어서 활용한다. 최대 힙인 이유는 우리가 가능한 연산이 빼기 연산이기 때문에, 가장 큰 친구부터 빼는 것이 유리하기 때문이다. 아무튼 이 최대 힙을 가지고 유지하고 싶은 불변식은 바로 최대 힙에서 두 번 pop한 결과가 같지 않도록 하는 것이다. 즉, 가장 큰 두 빈도가 같으면, 이 중 한 친구를 1씩 빼면서 다시 힙에 넣어서 두 빈도가 같지 않을 때까지 반복하는 것이다. 굉장한 아이디어다. 이거는 나중에 유사한 문제가 나왔을 때에도 써먹을 수 있을 것 같아서 기록해둔다.

def minDeletions(s):
    maxheap = [-f for f in Counter(s).values()]
    heapq.heapify(maxheap)
    deleted = 0
    while len(maxheap) >= 2:
        top = heapq.heappop(maxheap)
        if top != 0 and top == maxheap[0]:
            deleted += 1
            heapq.heappush(maxheap, top + 1)
    return deleted

• 참고로 파이썬에서 힙을 만드는 가장 빠른 방법은 일일이 값을 heapq.heapush로 넣는 것이 아니라, 일단 값을 리스트에 다 때려박은 다음에 heapq.heapify를 호출하는 것이다. 얼핏 생각하면 “어차피 모든 원소에 대해서 (O(N)) 힙을 하나씩 푸시하는 건 똑같을테니(O(logN)) 복잡도는 둘다 O(NlogN)아닌가?” 라고 생각되겠지만, 이게 생각보다 이론적인 복잡함이 있고 아무튼 결론은 일일이 푸시하는 것보다 리스트를 힙 성질이 유지되도록 바꾸는 것이 더 빠르다고 한다. 정확한 복잡도 O(N)이라고 하는데 사실 식을 유도해서 증명한 건 이해못했고 아무튼 더 빠르다 라고만 알고 쓴다.
• 최대 힙에 원소가 최소 2개는 있어야 두 빈도가 같은지 확인할 수 있기 때문에 루프의 조건식은 두 개 이상일 때에만 이다.
• 파이썬은 최대힙이 없기 때문에 그냥 부호를 뒤집어서 사용했다. 그래서 실제로는 빼는 연산이지만 여기서는 더하는 연산으로 바꿨다.
• 마찬가지로 빈도가 0이 되는 케이스는 무시한다.

이렇게하면 실제 복잡도는 O(N + K^2logK)로 해시셋보다는 약간 나빠지지만 logK가 별로 크지 않아서 거의 차이는 없을 것으로 생각된다.