문제 개요
문자열 s가 주어졌을 때, 서로 다른 두 문자가 같은 빈도(등장 횟수)를 가지지 않으면 이 문자열을 '좋은(good) 문자열'이라고 정의합니다. 즉, 모든 문자의 등장 횟수가 서로 달라야 한다는 조건입니다.
우리의 목표는 주어진 문자열을 좋은 문자열로 만들기 위해 삭제해야 하는 문자의 최소 개수를 구하는 것입니다.
예시
입력이 s = "ssstttuu"라고 가정해 보겠습니다. 현재 상태에서 's'는 3번, 't'는 3번, 'u'는 2번 등장하므로 's'와 't'의 빈도가 같아 좋은 문자열이 아닙니다.
't' 하나를 삭제하면 s: 3, t: 2, u: 2가 되지만, 여전히 't'와 'u'의 빈도가 같습니다. 따라서 't' 또는 'u' 중 하나를 추가로 삭제해야 하며, 최종적으로 필요한 최소 삭제 횟수는 2입니다.
해결 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- 각 문자의 빈도를 저장하는 맵(Counter)을 생성합니다.
- 빈도 값들을 오름차순으로 정렬한 리스트를 만듭니다.
- 리스트를 순회하면서 인접한 두 빈도 값이 같고 0이 아니라면, 앞쪽 값을 1 감소시키고 삭제 횟수를 1 증가시킵니다.
- 값을 감소시킨 뒤에는 그 앞의 요소들과도 비교하여 중복이 발생하지 않도록 연쇄적으로 확인하고 조정합니다. 이때마다 삭제 횟수를 함께 증가시킵니다.
- 모든 순회가 끝나면 누적된 삭제 횟수를 반환합니다.
구현 코드
다음은 위 알고리즘을 Python으로 구현한 예제입니다.
from collections import Counter
def solve(s):
val = Counter(s)
res = 0
numlist = sorted([i for i in val.values()])
for i in range(len(numlist)-1):
if numlist[i] and numlist[i] == numlist[i+1]:
numlist[i] -= 1
res += 1
k = i-1
m = i
while numlist[m] and numlist[m] == numlist[k]:
numlist[k] -= 1
k -= 1
m -= 1
res += 1
return res
s = "ssstttuu"
print(solve(s))실행 결과
입력
"ssstttuu"
출력
2
동작 원리 설명
이 알고리즘의 핵심은 빈도를 오름차순으로 정렬한 후 인접 요소를 비교하는 것입니다. 정렬된 상태에서 중복이 발견되면 작은 쪽 값을 줄이는 것이 전체 삭제 횟수를 최소화하는 전략입니다.
값을 줄인 결과가 더 앞쪽의 빈도와 충돌할 수 있으므로, 내부 while 루프를 통해 왼쪽 방향으로 계속 검사하며 충돌이 없어질 때까지 값을 감소시킵니다. 이 과정에서 매번 삭제 횟수(res)가 1씩 늘어나며, 최종적으로 모든 빈도가 고유해질 때까지 필요한 최소 삭제 수를 얻게 됩니다.
시간 복잡도는 빈도 정렬에 O(n log n), 중복 해소 과정에 최대 O(k²)(k는 서로 다른 빈도 값의 개수)가 소요될 수 있으며, 일반적인 입력 크기에서는 충분히 효율적으로 동작합니다.