인코딩된 문자열 S가 하나 주어져 있다고 가정해 보겠습니다. 이 문자열을 한 번에 한 글자씩 읽으면서 다음 규칙에 따라 디코딩된 문자열을 테이프에 기록해야 합니다.
- 읽은 문자가 영문자라면 해당 문자를 그대로 테이프에 씁니다.
- 읽은 문자가 숫자 d라면 지금까지 테이프에 기록된 전체 내용을 정확히 d − 1번 더 반복해서 이어 씁니다.
이제 인코딩된 문자열 S와 인덱스 K가 주어졌을 때, 디코딩된 문자열에서 K번째(인덱스는 1부터 시작) 문자를 찾아 반환하는 것이 문제의 목표입니다.
예를 들어 문자열이 "hello2World3"이고 k = 10이라면 출력은 "o"입니다. 디코딩된 문자열은 "hellohelloWorldhellohelloWorldhellohelloWorld"가 되며, 그중 10번째 문자가 바로 "o"이기 때문입니다.
접근 방법
디코딩된 문자열은 입력이 조금만 커져도 길이가 기하급수적으로 늘어날 수 있습니다. 따라서 전체 문자열을 실제로 생성하지 않고 역방향 탐색(역추적) 기법으로 답을 찾는 것이 핵심입니다. 절차는 다음과 같습니다.
- 1단계 – 전체 길이 계산: size := 0으로 초기화한 뒤 문자열 s를 앞에서부터 순회합니다. 문자가 숫자면 size := size × (그 숫자의 정숫값), 영문자면 size := size + 1로 갱신합니다. 순회가 끝나면 size는 디코딩된 문자열의 전체 길이가 됩니다.
- 2단계 – 뒤에서부터 역순 순회: i를 len(s) − 1부터 0까지 하나씩 줄여 가며 다음을 수행합니다.
- k := k mod size로 갱신합니다.
- s[i]가 영문자이고 k = 0이면 s[i]를 정답으로 반환합니다.
- s[i]가 숫자라면 size := size ÷ (그 숫자의 정숫값), 영문자라면 size := size − 1로 되돌려 직전 상태의 테이프 길이를 복원합니다.
- 모든 문자를 확인했는데도 답을 찾지 못했다면 빈 문자열을 반환합니다.
이 방식이 동작하는 이유는 간단합니다. 뒤에서부터 한 글자씩 제거하며 테이프 길이를 이전 상태로 되돌리는 과정에서, 어느 시점의 k mod size가 0이 되는 영문자 자리가 곧 디코딩된 문자열에서 K번째에 해당하는 문자이기 때문입니다.
예제 코드
class Solution(object):
def decodeAtIndex(self, s, k):
"""
:type s: str
:type k: int
:rtype: str
"""
size = 0
for i in s:
if i.isdigit():
size *= int(i)
else:
size += 1
for i in range(len(s) - 1, -1, -1):
k %= size
if s[i].isalpha() and k == 0:
return s[i]
if s[i].isalpha():
size -= 1
else:
size //= int(s[i])
return ""
ob = Solution()
print(ob.decodeAtIndex("hello2World3", 10))
입력
"hello2World3" 10
출력
o
복잡도 분석
- 시간 복잡도: O(N) — 인코딩된 문자열을 정방향과 역방향으로 최대 두 번 순회합니다.
- 공간 복잡도: O(1) — 디코딩된 문자열을 저장하지 않고 몇 개의 변수만 사용합니다.