C++로 해독된 문자열에서 k번째 문자 찾기 – Set 2

개념

이 문제에서는 인코딩된 문자열이 주어지며, 부분 문자열의 반복은 해당 부분 문자열 뒤에 반복 횟수를 붙이는 방식으로 표현됩니다. 예를 들어 인코딩된 문자열이 "pq2rs2"이고 k=5라면, 해독된 문자열은 "pqpqrsrs"가 되고 5번째 문자는 'r'이므로 출력 결과는 'r'입니다.

여기서 한 가지 주의할 점은 인코딩된 부분 문자열의 반복 빈도가 두 자릿수 이상일 수 있다는 것입니다. 예를 들어 "pq12r3"에서 pq는 12번 반복됩니다. 또한 빈도 수에는 선행 0(leading zero)이 존재하지 않습니다.

입력 예시

"p2q2r3", k = 6

출력

r

해독된 문자열은 "ppqqrrr"입니다.

입력 예시

"pq4r2ts3", k = 11

출력

t

해독된 문자열은 "pqpqpqpqrrtststs"입니다.

접근 방법

문자열을 실제로 해독하지 않고도 k번째 문자를 찾을 수 있으며, 단계별 알고리즘은 다음과 같습니다.

• 두 개의 포인터를 활용합니다. 한 포인터는 부분 문자열의 시작 위치에 고정하고, 다른 포인터는 숫자가 나올 때까지 이동시켜 현재 부분 문자열의 길이를 구합니다.
• 두 번째 포인터를 계속 이동하여 알파벳이 나올 때까지 진행하면, 앞선 부분 문자열의 반복 빈도를 구할 수 있습니다.
• 부분 문자열이 반복되었을 때의 전체 길이는 원래 길이에 빈도를 곱하여 계산합니다.
• 계산된 길이가 k보다 작다면, 원하는 문자는 그다음 부분 문자열에 있습니다. 이때 k에서 해당 길이를 빼면 아직 확인해야 할 문자의 개수를 계속 추적할 수 있습니다.
• 반대로 길이가 k보다 크거나 같다면, 원하는 문자는 현재 부분 문자열 안에 있습니다. k는 1부터 시작하는 인덱스이므로 1을 감소시킨 뒤 원래 부분 문자열의 길이로 나머지 연산을 수행합니다. 그러면 첫 번째 포인터가 가리키는 위치에서 k번째 문자가 곧 정답이 됩니다.

구현 예제 (C++)

// 해독된 문자열에서 K번째 문자를 찾는 C++ 프로그램
#include <bits/stdc++.h>
using namespace std;

// 인코딩된 문자열에서 K번째 문자를 찾는 함수
char encodedChar(string str, int k){
    int a, b;
    int m = str.length();
    // 부분 문자열의 길이를 저장
    int len1;
    // 반복되었을 때의 부분 문자열 길이를 저장
    int num1;
    // 부분 문자열의 반복 빈도를 저장
    int freq1;

    a = 0;
    while (a < m) {
        b = a;
        len1 = 0;
        freq1 = 0;

        // 숫자가 나오기 전까지 문자열을 순회하며
        // 부분 문자열의 길이를 구합니다.
        while (b < m && isalpha(str[b])) {
            b++;
            len1++;
        }

        // 앞선 부분 문자열의 반복 빈도를 구합니다.
        while (b < m && isdigit(str[b])) {
            freq1 = freq1 * 10 + (str[b] - '0');
            b++;
        }

        // 부분 문자열이 반복되었을 때의 길이를 구합니다.
        num1 = freq1 * len1;

        // 반복된 부분 문자열의 길이가 k보다 작으면
        // 원하는 문자는 다음 부분 문자열에 있습니다.
        // 방문해야 할 문자 수를 추적하기 위해
        // k에서 반복된 부분 문자열의 길이를 뺍니다.
        if (k > num1) {
            k -= num1;
            a = b;
        }
        // 반복된 부분 문자열의 길이가 k보다 크거나 같으면
        // 원하는 문자는 현재 부분 문자열 안에 있습니다.
        else {
            k--;
            k %= len1;
            return str[a + k];
        }
    }

    // 문자열에 반복이 없는 경우를 위한 처리입니다.
    // 예: str="abced"
    return str[k - 1];
}

// 드라이버 코드
int main(){
    string str1 = "pqpqpqpqrrtststs";
    int k1 = 11;
    cout << encodedChar(str1, k1) << endl;

    string str2 = "p2q2r3";
    int k2 = 6;
    cout << encodedChar(str2, k2) << endl;

    return 0;
}

실행 결과

t
r

복잡도 분석

이 알고리즘은 인코딩된 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)(n은 인코딩된 문자열의 길이)이며, 추가적인 메모리를 사용하지 않으므로 공간 복잡도는 O(1)입니다. 문자열을 실제로 해독하면 지수적으로 길이가 늘어날 수 있지만, 이 방법은 해독 과정 없이 두 포인터만으로 정답을 찾기 때문에 매우 효율적입니다.