Python으로 문자열을 최대 K개의 고유 문자로 만들기 위한 최소 변경 횟수 구하기

문제 개요

소문자 알파벳으로 구성된 문자열 s와 정수 k가 주어졌을 때, 결과 문자열이 최대 k개의 서로 다른 고유 문자를 갖도록 만들기 위해 필요한 최소 변경 횟수를 구하는 것이 목표입니다. 여기서 '변경'이란 문자열 내의 한 문자를 임의의 다른 문자로 바꾸는 작업을 의미합니다.

예를 들어 입력이 s = "wxxyyzzxx", k = 3이라면 정답은 1입니다. 문자 'w'를 'x', 'y', 'z' 중 하나로 바꾸면 문자열에는 x, y, z 세 종류의 고유 문자만 남기 때문입니다.

해결 접근 방식

이 문제는 그리디(Greedy) 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• count: 문자열 s에 등장하는 각 문자별 빈도수를 저장한 맵(Counter)

• sv: 빈도수 값들을 오름차순으로 정렬한 리스트

• ans: 누적 변경 횟수 (초깃값 0)

• i를 0부터 (고유 문자 수 − k − 1)까지 반복하며 ans에 sv[i]를 더함

• ans 반환

즉, 고유 문자의 개수가 k개를 초과할 경우, 등장 빈도가 가장 낮은 문자부터 차례대로 다른 문자로 변경하면 전체 변경 횟수를 최소화할 수 있습니다. 드물게 등장하는 문자를 없애는 것이 가장 적은 비용으로 조건을 충족하는 방법이기 때문입니다.

구현 예제

from collections import Counter

class Solution:
    def solve(self, s, k):
        count = Counter(s)
        sv = sorted(count.values())
        ans = 0
        for i in range(len(count) - k):
            ans += sv[i]
        return ans

ob = Solution()
s = "wxxyyzzxx"
k = 3
print(ob.solve(s, k))

입력

"wxxyyzzxx", 3

출력

1

동작 원리 살펴보기

예제 문자열 "wxxyyzzxx"의 문자별 빈도는 w: 1, x: 4, y: 2, z: 2로, 고유 문자는 총 4개입니다. k = 3 조건을 맞추려면 하나를 줄여야 하는데, 빈도가 가장 낮은 'w'(1회)를 변경하면 되므로 최소 변경 횟수는 1이 됩니다.

이 알고리즘의 시간 복잡도는 문자열 길이를 n, 고유 문자 수를 m이라 할 때 O(n + m log m)입니다. 문자열을 한 번 순회해 빈도를 세고(O(n)), 빈도값을 정렬하는 데 O(m log m)이 소요되기 때문입니다.