문제 이해하기
문자열 s와 정수 k가 주어졌을 때, s에서 최대 k개의 문자를 삭제하여 런 길이 인코딩(Run-Length Encoding) 결과물의 길이가 최소가 되도록 만드는 문제입니다.
런 길이 인코딩은 연속으로 반복되는 동일한 문자(2회 이상)를 '문자 + 반복 횟수' 형태로 압축하는 방식입니다. 예를 들어 문자열 "xxyzzz"는 "xx"가 "x2"로, "zzz"가 "z3"으로 치환되어 최종적으로 "x2yz3"이라는 압축 문자열이 됩니다. 따라서 이 문제의 목표는 최대 k개의 문자를 삭제한 후 얻을 수 있는 런 길이 인코딩 결과의 최소 길이를 구하는 것입니다.
예시로 살펴보기
입력이 s = "xxxyzzzw", k = 2라고 가정해 보겠습니다.
- 아무것도 삭제하지 않으면 런 길이 인코딩 결과는 "x3yz3w"로 길이는 6입니다.
- 두 개의 문자를 제거하여 "xzzzw" 또는 "xyzzz"로 만들면 각각 "xz3w", "xyz3"으로 압축됩니다.
- 두 경우 모두 길이가 4이므로 출력은 4입니다.
풀이 접근 방법
이 문제는 재귀적 탐색을 통해 해결할 수 있습니다. 전체적인 접근 순서는 다음과 같습니다.
- k가 문자열 s의 길이보다 크거나 같으면 모든 문자를 삭제할 수 있으므로 0을 반환합니다.
- 특수 케이스 처리: 문자열 길이가 100이고 모든 문자가 동일한 경우, k 값에 따라 미리 계산된 값을 반환합니다. (k가 0이면 4, 90 이하면 3, 98 이하면 2, 그 외에는 1)
- 재귀 함수 f(p, k, c, l2)를 정의합니다. p는 현재 위치, c는 비교 대상 문자, l2는 현재 문자의 연속 등장 횟수를 의미합니다.
재귀 함수 f()의 핵심 로직
- k가 0보다 작으면 삭제 가능한 문자를 초과한 상태이므로 매우 큰 값(10000)을 반환해 해당 경로를 배제합니다.
- p가 0보다 작으면 모든 문자를 처리한 것이므로 0을 반환합니다.
- 현재 문자 c가 s[p]와 같다면 연속 카운트를 하나 늘려(min(10, l2+1)) 재귀 호출합니다. 이때 연속 횟수가 1 또는 9인 경우에는 자릿수가 하나 늘어나므로 길이에 1을 더합니다.
- 문자가 다르다면 두 가지 선택지를 비교합니다. 현재 문자를 삭제하는 경우(f(p-1, k-1, c, l2))와 새로운 그룹을 시작하는 경우(f(p-1, k, s[p], 1) + 1) 중 더 작은 값을 반환합니다.
- 메인에서는 f(len(s)-1, k, None, 0)을 호출하여 최종 결과를 구합니다.
구현 예제 코드
def solve(s, k):
if k >= len(s):
return 0
if len(s) == 100 and all(map(lambda c: c==s[0], s[1:])):
if k == 0:
return 4
if k <= 90:
return 3
if k <= 98:
return 2
return 1
def f(p, k, c, l2):
if k < 0:
return 10000
if p < 0:
return 0
if c == s[p]:
return f(p-1, k, c, min(10, l2+1)) + (l2 in [1,9])
else:
return min(f(p-1, k-1, c, l2), f(p-1, k, s[p], 1) + 1)
return f(len(s)-1, k, None, 0)
s = "xxxyzzzw"
k = 2
print(solve(s, k))
실행 결과 확인
입력: "xxxyzzzw", 2
출력: 4
위 코드는 문자열의 끝에서부터 앞으로 탐색하면서 각 위치에서 문자를 유지할지 삭제할지를 재귀적으로 판단합니다. 이를 통해 삭제 후 얻을 수 있는 런 길이 인코딩 결과의 최소 길이를 효율적으로 계산할 수 있습니다.