소문자로 이루어진 문자열 s와 정수 k가 주어졌다고 가정해 봅시다. 여기서 '런-길이 인코딩(Run-Length Encoding)'은 반복되는 연속된 문자를 개수와 문자 형태로 표현하는 방식입니다. 예를 들어 문자열 "aaabbc"는 "3a2bc"로 인코딩됩니다. 이때 "c"처럼 한 번만 나타나는 문자에는 "1c"라고 표기하지 않고 그대로 씁니다.
우리가 해야 할 작업은 다음과 같습니다. 먼저 문자열 s에서 임의의 k개의 연속된 문자를 제거한 뒤, 결과 문자열을 런-길이 인코딩했을 때 얻을 수 있는 최소 길이를 구하는 것입니다.
예제로 이해하기
입력이 s = "xxxxxyyxxxxxzzxxx", k = 2라고 가정해 보겠습니다. 이 경우 출력은 6이 됩니다. 선택할 수 있는 명백한 방법은 "yy"를 제거하거나 "zz"를 제거하는 두 가지입니다.
- "yy"를 제거하면 → "10x2z3x"가 되어 길이는 7입니다.
- "zz"를 제거하면 → "5x2y8x"가 되어 길이는 6입니다. 이것이 가장 작은 값입니다.
해결 방법
이 문제는 접두사(prefix)와 접미사(suffix) 정보를 미리 계산해 두는 방식으로 효율적으로 해결할 수 있습니다. 단계별로 살펴보겠습니다.
1. calc_cost() 함수 정의
런-길이 l이 인코딩에서 차지하는 비용(길이)을 계산합니다.
- l이 0이면 0을 반환합니다.
- l이 1이면 1을 반환합니다. (문자 하나만 표기)
- 그 외의 경우에는 숫자 자릿수 + 문자 1개, 즉 len(str(l)) + 1을 반환합니다.
2. prefix() 함수 정의
각 위치까지의 누적 인코딩 비용과 현재 진행 중인 런의 길이를 저장한 리스트를 만듭니다.
- pre := [0, 0] 쌍으로 시작하는 리스트
- last := null
- s의 각 문자 c에 대해:
- c가 last와 같으면 → pre에 (이전 비용, 이전 런 길이 + 1)을 추가
- 다르면 → pre에 (이전 비용 + calc_cost(이전 런 길이), 1)을 추가
- last := c로 갱신 후 반복
- 완성된 pre를 반환
3. 메인 로직
- pre := prefix(s) — 정방향 누적 비용 계산
- suf := 역순 문자열에 대한 prefix 결과를 다시 뒤집은 값 — 역방향 누적 비용 계산
- ans := 무한대로 초기화
- i를 0부터 (len(s) - k)까지 순회하며:
- j := i + k (제거 구간의 끝)
- (left, midl) := pre[i], (right, midr) := suf[j]
- cost := left + right
- c1 := i > 0일 때 s[i-1], 아니면 None
- c2 := j < len(s)일 때 s[j], 아니면 None
- c1 == c2라면 제거된 양쪽 런이 합쳐지므로 cost += calc_cost(midl + midr)
- 그렇지 않으면 cost += calc_cost(midl) + calc_cost(midr)
- ans := ans와 cost 중 최솟값
- ans 반환
핵심 아이디어는 제거 구간 [i, i+k)를 기준으로 왼쪽 부분과 오른쪽 부분의 인코딩 비용을 각각 누적 배열에서 O(1)에 가져오고, 경계에서 잘린 런(midl, midr)의 비용만 별도로 처리하는 것입니다. 특히 제거 후 양쪽 끝의 문자가 같아진다면 두 런이 하나로 합쳐진다는 점을 반드시 고려해야 합니다.
구현 코드
아래 파이썬 코드를 통해 더 자세히 이해해 보겠습니다.
def calc_cost(l):
if l == 0:
return 0
if l == 1:
return 1
else:
return len(str(l)) + 1
class Solution:
def solve(self, s, k):
def prefix(s):
pre = [[0, 0]]
last = None
for c in s:
if c == last:
pre.append([pre[-1][0], pre[-1][1] + 1])
else:
pre.append([pre[-1][0] + calc_cost(pre[-1][1]), 1])
last = c
return pre
pre = prefix(s)
suf = prefix(s[::-1])[::-1]
ans = float("inf")
for i in range(len(s) - k + 1):
j = i + k
left, midl = pre[i]
right, midr = suf[j]
cost = left + right
c1 = s[i - 1] if i > 0 else None
c2 = s[j] if j < len(s) else None
if c1 == c2:
cost += calc_cost(midl + midr)
else:
cost += calc_cost(midl) + calc_cost(midr)
ans = min(ans, cost)
return ans
ob = Solution()
s = "xxxxxyyxxxxxzzxxx"
print(ob.solve(s, 2))입력
s = "xxxxxyyxxxxxzzxxx", k = 2
출력
6
정리
이 알고리즘은 모든 제거 위치를 완전 탐색하면서도 누적 비용 배열 덕분에 전체 시간 복잡도를 O(n²) 수준으로 유지할 수 있습니다. 문자열 압축 문제에서 '경계에서 런이 합쳐지는 경우'를 놓치기 쉬운데, c1 == c2 조건 처리가 바로 그 핵심 포인트입니다. 실제 코딩 테스트에서도 자주 등장하는 패턴이니 꼭 기억해 두세요.