C++로 문자열 복호화 후 k번째 문자 찾는 방법

이 튜토리얼에서는 암호화된 문자열을 복호화한 후 k번째 문자를 찾는 프로그램을 C++로 구현하는 방법을 알아보겠습니다.

문제 정의

알파벳 문자와 숫자가 섞여 있는 문자열과 정수 K가 주어집니다. 여기서 숫자는 바로 앞에 있는 문자(들)가 반복되는 횟수를 의미합니다. 예를 들어 "ab2c3"은 복호화하면 "ab"가 2번, "c"가 3번 반복되어 "ababccc"가 됩니다.

우리의 목표는 실제로 전체 문자열을 펼쳐 만들지 않고도, 복호화된 문자열에서 K번째 위치에 해당하는 문자를 효율적으로 찾아내는 것입니다.

접근 방식

전체 복호화 문자열을 메모리에 생성하면 문자열이 매우 길어질 수 있으므로 비효율적입니다. 대신 다음과 같은 논리를 사용합니다.

문자열을 왼쪽부터 순회하면서 알파벳을 만나면 현재까지의 유효 길이(total_len)를 1씩 증가시킵니다.
숫자를 만나면 연속된 숫자를 하나의 정수 n으로 변환하여, 현재 길이가 n배가 된다고 계산합니다.
K가 확장된 길이 범위 안에 들어오면, 모듈로 연산(k % total_len)으로 원본 문자열 내의 해당 위치를 구한 뒤 재귀 호출로 답을 얻습니다.

구현 예제

#include <cstdlib>
#include <iostream>
using namespace std;

// 복호화된 문자열에서 k번째 문자 찾기
char findKthChar(string s, int k) {
    int len = s.length();
    int i = 0;
    int total_len = 0;
    while (i < len) {
        if (isalpha(s[i])) {
            total_len++;
            if (total_len == k)
                return s[i];
            i++;
        }
        else {
            // 연속된 숫자를 하나의 반복 횟수로 변환
            int n = 0;
            while (i < len && !isalpha(s[i])) {
                n = n * 10 + (s[i] - '0');
                i++;
            }
            int next_total_len = total_len * n;
            if (k <= next_total_len) {
                // 원본 문자열 내 위치 계산 후 재귀 호출
                int pos = k % total_len;
                if (!pos) {
                    pos = total_len;
                }
                return findKthChar(s, pos);
            }
            else {
                total_len = next_total_len;
            }
        }
    }
    return -1;
}

int main() {
    string s = "ab2c3";
    int k = 5;
    cout << findKthChar(s, k);
    return 0;
}

실행 결과

동작 설명

입력 문자열 "ab2c3"과 k = 5가 주어졌을 때 프로그램의 동작 흐름은 다음과 같습니다.

'a'와 'b'를 지나며 total_len이 2가 됩니다.
숫자 '2'를 만나 확장 길이가 4가 되지만, k = 5는 아직 범위를 벗어나므로 total_len을 4로 갱신합니다.
'c'를 지나 total_len이 5가 되고, k = 5와 일치하므로 'c'를 반환합니다.

이 방식은 복호화된 문자열을 실제로 생성하지 않기 때문에, 반복 횟수가 매우 큰 경우에도 O(n) 수준의 시간 복잡도로 효율적으로 동작합니다.