[LeetCode - 916] Decoded String at Index - C++

분류: 문자열 /

 

문제

916. Decoded String at Index

You are given an encoded string s. To decode the string to a tape, the encoded string is read one character at a time and the following steps are taken:

• If the character read is a letter, that letter is written onto the tape.
• If the character read is a digit d, the entire current tape is repeatedly written d - 1 more times in total.

Given an integer k, return the kth letter (1-indexed) in the decoded string.

 

Example 1:

Input: s = "leet2code3", k = 10
Output: "o"
Explanation: The decoded string is "leetleetcodeleetleetcodeleetleetcode".
The 10th letter in the string is "o".

Example 2:

Input: s = "ha22", k = 5
Output: "h"
Explanation: The decoded string is "hahahaha".
The 5th letter is "h".

Example 3:

Input: s = "a2345678999999999999999", k = 1
Output: "a"
Explanation: The decoded string is "a" repeated 8301530446056247680 times.
The 1st letter is "a".

 

Constraints:

• 2 <= s.length <= 100
• s consists of lowercase English letters and digits 2 through 9.
• s starts with a letter.
• 1 <= k <= 109
• It is guaranteed that k is less than or equal to the length of the decoded string.
• The decoded string is guaranteed to have less than 263 letters.

 

풀이

string decodeAtIndex(string s, int k) {
    long long len = 0;
    for(char c:s) {
        if(c > '0' && c <= '9') len *= c - '0';
        else len++;
    }

    string ans = "";
    for(int i=s.length()-1; i>=0; i--) {
        if(isdigit(s[i])) { // c: 숫자 문제 축소
            len /= s[i] - '0';
            k %= len;
        } else if(k == 0 || k == len) { // 답
            ans += s[i];
            break;
        } else { // c: 문자 문제 축소
            len--;
        }
    }
    return ans;
}

문제에서 시키는 데로 `s`를 decode 해서 decoded string을 만든 뒤 k번째 문자를 찾으면 쉽지만 당연히 안된다.

decoded 된 `s`의 최대 길이는 2⁶³이고 c++의 char의 크기는 1byte이므로 s는 최대 2⁶³bytes. 메모리 초과.

따라서 길이가 100 이하인 encoded string `s`로 문제를 해결해야 한다.

 

예시들을 직접 수행해 보면 modulo가 떠오른다. `s = leet2, k = 5`는 `s = leet, k = 1`과 같은 문제다.

1. decoded string의 전체 길이(`len`)를 계산(첫 번째 for문) 
2. `s` reverse traversal: `c`
   1. `c`가 숫자(`n`)라면 나누기로 문제 축소(`len /= n`, `k %= len`)
   2. `c`가 문자라면
      1. 현재 문자가 `k`번째 문자라면 답(`if(k == 0 || k == len)`)
      2. 아니라면 탑색 범위를 하나 줄여 문제 축소(`len--`)

`len`은 가상의 decoded string의 길이이며 탐색 범위를 의미한다. 탐색 범위를 줄여가며 답을 찾는다.

`c`가 숫자`n`이라면 `n`으로 `len`을 나누어 문제를 축소한다. 축소된 탐색범위에 맞춰 답의 위치인 `k`도 변경한다.(`k %= len`)

 

`k`는 가상의 decoded string에서 답의 위치를 나타낸다.

`k`는 `len`의 모듈로 값이므로 `k == 0`의 의미는 숫자 다음 나타난(숫자 바로 앞) 문자가 답이라는 뜻이다.

즉 `k == 0`도 결국 `k == len`과 같은 의미다.

 

`c`가 문자라면 답인지 확인하고 답이 아니라면 `c`를 버리고 문제를 축소한다. 이 경우 `k < len`이다.