문제 소개
인코딩된 문자열이 하나 주어졌다고 가정해 보겠습니다. 이 문자열에서는 부분 문자열의 반복이 "부분 문자열 + 반복 횟수" 형태로 표현됩니다. 예를 들어 문자열이 ab2cd2라면 실제 문자열은 ababcdcd를 의미합니다. 이때 k = 4가 주어지면 디코딩된 문자열에서 4번째 문자인 b를 반환해야 합니다.
접근 방식
이 문제는 다음 단계로 해결할 수 있습니다.
- 빈 디코딩 문자열(decrypted)을 준비합니다.
- 원본 문자열을 처음부터 읽으면서 알파벳으로 된 부분 문자열과 그 뒤에 따라오는 반복 횟수를 하나씩 추출합니다.
- 현재 부분 문자열을 반복 횟수만큼 디코딩 문자열에 이어 붙입니다.
- 원본 문자열이 모두 소진될 때까지 위 과정을 반복한 뒤, 디코딩된 문자열에서 k번째 문자를 반환합니다.
C++ 예제 코드
#include<iostream>
using namespace std;
char findKthCharacter(string str,int k) {
string decrypted = "";
string temp;
int occurrence = 0;
for (int i=0; str[i]!='\0'; ){
temp = "";
occurrence = 0;
while (str[i]>='a' && str[i]<='z'){
temp += str[i];
i++;
}
while (str[i]>='1' && str[i]<='9') {
occurrence = occurrence*10 + str[i] - '0';
i++;
}
for (int j=1; j<=occurrence; j++)
decrypted = decrypted + temp;
}
if (occurrence==0)
decrypted = decrypted + temp;
return decrypted[k-1];
}
int main() {
string str = "ab4c12ed3";
int k = 21;
cout << k << "th character in decrypted string: " << findKthCharacter(str, k);
}
코드 동작 설명
findKthCharacter 함수는 인코딩된 문자열과 k 값을 입력받아 다음과 같이 동작합니다.
- 알파벳 소문자를 만나는 동안에는 해당 문자들을
temp에 계속 누적합니다. - 숫자를 만나는 동안에는 자릿수를 고려해
occurrence에 반복 횟수로 변환하여 저장합니다(예: "12" → 12). - 부분 문자열과 횟수를 모두 읽으면
temp를occurrence번 만큼decrypted에 추가합니다. - 반복 횟수가 명시되지 않은 경우(
occurrence == 0)에는 부분 문자열을 한 번만 추가합니다. - 마지막으로
decrypted[k-1]을 반환하여 k번째 문자를 구합니다.
실행 결과
예제에서 사용한 문자열 ab4c12ed3은 다음과 같이 디코딩됩니다.
ab4→abababab(1~8번째 문자)c12→cccccccccccc(9~20번째 문자)ed3→ededed(21~26번째 문자)
따라서 k = 21일 때 21번째 문자는 e입니다.
21th character in decrypted string: e
복잡도 및 최적화 팁
위 방식은 디코딩된 문자열 전체를 메모리에 저장하므로, 최종 문자열의 길이를 L이라 할 때 시간·공간 복잡도는 모두 O(L)입니다. 만약 k번째 문자 하나만 필요하다면 전체 문자열을 실제로 만들지 않고 각 세그먼트의 누적 길이만 추적하여 k가 어느 세그먼트에 속하는지만 확인하면 됩니다. 이렇게 하면 메모리 사용량을 크게 줄여 더 큰 입력에서도 효율적으로 동작합니다.