인코딩된 문자열에서는 부분 문자열의 반복이 "부분 문자열 뒤에 반복 횟수"를 붙이는 방식으로 표현됩니다. 예를 들어 문자열이 "pq2rs2"이고 k=5라면, 해독된 문자열은 "pqpqrsrs"이며 5번째 문자는 'r'입니다. 이때 반복 횟수가 한 자리 숫자를 넘는 두 자리 이상의 값일 수도 있다는 점을 반드시 고려해야 합니다.
예를 들어 입력이 string = "pq4r2ts3", k = 11이라면 해독 결과는 "pqpqpqpqrrtststs"가 되고, 11번째 문자인 't'가 출력됩니다.
문제 해결 접근 방법
다음 단계를 따라 문제를 해결할 수 있습니다.
- 결괏값을 저장할 encoded를 빈 문자열로, occurrence와 i를 각각 0으로 초기화합니다.
- i가 문자열 길이보다 작은 동안 아래 과정을 반복합니다.
- temp를 빈 문자열로, occurrence를 0으로 초기화합니다.
- i가 문자열 길이보다 작고 str[i]가 알파벳인 동안 temp에 str[i]를 이어 붙이고 i를 1씩 증가시킵니다.
- i가 문자열 길이보다 작고 str[i]가 숫자인 동안 occurrence = occurrence × 10 + (str[i]의 숫자 값) 공식으로 반복 횟수를 누적합니다. 이 방식 덕분에 두 자리 이상의 반복 횟수도 올바르게 읽어낼 수 있습니다.
- j를 1부터 occurrence까지 반복하며 encoded에 temp를 추가합니다.
- occurrence가 0이라면(반복 횟수가 생략된 경우) encoded에 temp를 한 번만 추가합니다.
- 모든 문자를 처리한 뒤 encoded[k - 1], 즉 해독된 문자열의 k번째 문자를 반환합니다.
예제 코드
아래 파이썬 구현을 보면 동작 방식을 더 쉽게 이해할 수 있습니다.
def find_kth_char(s, k):
encoded = ""
occurrence = 0
i = 0
while i < len(s):
temp = ""
occurrence = 0
# 1. 알파벳으로 된 부분 문자열 추출
while i < len(s) and 'a' <= s[i] <= 'z':
temp += s[i]
i += 1
# 2. 반복 횟수 추출 (두 자리 이상 숫자도 처리)
while i < len(s) and '0' <= s[i] <= '9':
occurrence = occurrence * 10 + ord(s[i]) - ord('0')
i += 1
# 3. 반복 횟수만큼 부분 문자열을 결괏값에 추가
for j in range(1, occurrence + 1):
encoded += temp
# 4. 반복 횟수가 없으면 한 번만 추가
if occurrence == 0:
encoded += temp
return encoded[k - 1]
s = "pq4r2ts3"
k = 11
print(find_kth_char(s, k))입력
"pq4r2ts3", 11
출력
t
정리
이 알고리즘은 문자열을 한 번만 순회하면서 알파벳 구간과 숫자 구간을 나누어 읽습니다. 숫자를 왼쪽부터 자릿수 단위로 누적하기 때문에 "a12b"처럼 반복 횟수가 두 자리인 경우에도 정확하게 해석됩니다. 해독된 문자열 전체를 직접 만드는 방식이므로 시간·공간 복잡도는 해독 결과의 길이에 비례하지만, 구현이 단순하고 직관적이어서 k번째 문자를 찾는 문제의 기본 해법으로 널리 활용됩니다.