문제 소개
문자열 s가 주어졌다고 가정해 봅시다. 이 문자열은 어떤 더 긴 원본 문자열을 인코딩한 결과입니다. 인코딩 규칙은 다음과 같습니다.
- n(t)는 문자열 t를 n번 반복하여 이어 붙인 결과를 의미합니다.
- t는 일반 문자열일 수도 있고, 또 다른 인코딩된 문자열이 재귀적으로 포함될 수도 있습니다.
예를 들어 입력이 s = "3(pi)2(3(am))0(f)1(u)"라면, 디코딩된 출력은 "pipipiamamamamamamu"가 됩니다. 각 부분을 살펴보면 다음과 같습니다.
3(pi)→pipipi2(3(am))→amamamamamam(내부의3(am)이 먼저amamam으로 확장되고, 그것이 2번 반복됨)0(f)→ 빈 문자열 (0번 반복이므로 제거됨)1(u)→u
접근 방법: 재귀적 파싱
이 문제는 재귀적으로 문자열을 파싱하면서 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 현재 위치를 가리키는 인덱스
i를 0으로 초기화합니다. parse()함수를 정의합니다. 이 함수는 닫는 괄호)를 만나거나 문자열 끝에 도달할 때까지 문자를 읽습니다.- 숫자를 만나면 연속된 숫자들을 모아 반복 횟수
d를 계산하고, 여는 괄호(를 건너뛴 뒤parse()를 재귀 호출하여 내부 문자열을 얻습니다. 그 후 닫는 괄호)를 건너뛰고, 해당 세그먼트를d번 반복하여 결과에 추가합니다. - 숫자가 아닌 일반 문자라면 그대로 결과 리스트에 추가하고 인덱스를 증가시킵니다.
- 마지막으로 결과 리스트의 모든 요소를 이어 붙여 반환합니다.
구현 예제
아래 코드로 실제 구현 과정을 확인해 보겠습니다.
class Solution:
def solve(self, s):
i = 0
def parse():
nonlocal i
ans = []
while i < len(s) and s[i] != ")":
if s[i].isdigit():
d = 0
# 연속된 숫자를 읽어 반복 횟수 계산
while s[i].isdigit():
d = 10 * d + int(s[i])
i += 1
i += 1 # '(' 건너뛰기
segment = parse() # 내부 문자열 재귀적으로 파싱
i += 1 # ')' 건너뛰기
ans.extend(segment for _ in range(d))
else:
ans.append(s[i])
i += 1
return "".join(ans)
return parse()
ob = Solution()
s = "3(pi)2(3(am))0(f)1(u)"
print(ob.solve(s))
입력
"3(pi)2(3(am))0(f)1(u)"
출력
pipipiamamamamamamu
코드 설명
nonlocal i 선언 덕분에 내부 함수 parse()에서 외부 변수 i를 직접 수정할 수 있습니다. 숫자가 여러 자리일 경우(예: 12(ab))에도 d = 10 * d + int(s[i]) 방식으로 올바르게 처리됩니다. 중첩된 괄호 구조는 재귀 호출을 통해 자연스럽게 해결되며, 각 재귀 호출은 자신이 속한 괄호 쌍의 범위만 처리하고 종료됩니다.
이 알고리즘의 시간 복잡도는 최종 디코딩된 문자열의 길이에 비례하며, 공간 복잡도 역시 결과 문자열과 재귀 호출 스택 깊이에 의해 결정됩니다.