[c++/LeetCode-Stack] 394. Decode String

 

 

 

난이도: Medium

키워드: Stack

문제

 

인코딩된 문자열이 주어지면 해당 문자열을 디코딩한 문자열을 반환합니다. 인코딩 규칙은 다음과 같습니다: 

 

k[인코딩된_문자열], 여기서 대괄호 내의 인코딩된 문자열이 k번 정확히 반복됩니다. 
k는 양의 정수임이 보장됩니다.

입력 문자열이 항상 유효하다고 가정할 수 있습니다. 추가적인 공백이나 대괄호가 잘 형성되어 있지 않습니다. 또한 원본 데이터에는 숫자가 포함되어 있지 않으며 숫자는 반복 횟수 k만을 위한 것입니다. 

예를 들어, 3a 또는 2[4]와 같은 입력은 없습니다. 테스트 케이스는 출력의 길이가 항상 10^5를 초과하지 않도록 생성됩니다.

 

입력 예시

 

Example 1:

Input: s = "3[a]2[bc]"
Output: "aaabcbc"

 

문제 원문: https://leetcode.com/problems/decode-string/description/

 

문제 풀이

 

- 괄호가 있는 문제는 기본적으로 stack 자료형을 사용하면 쉽게 풀 수 있다.

- 그래서 stack을 사용해서 문제를 풀었다.

- 별도의 stack 자료형을 두지 않고 vector<char>를 둬서 풀었는데, top() 조회는 `stack.back()` 으로, pop() 연산자는 `stack.erase(stack.end()-1)`로 구현하였다.

- 아이디어는 ]를 만날때까지의 정보를 모두 stack 에 저장하고, ]를 만나면 [를 만날때까지의 정보를 tmp_stack에 넣어두었다가. 이어서 나타나는 숫자 (이 때, 한자리 수가 아니기 때문에 while 문을 가지고 숫자 N을 찾음) 만큼 반복해서 stack에 넣어줬다.

- 최종적으로 stack 안에 담겨있는 값을 string으로 반환한다.

 

Runtime: 0ms Beats100.00%of users with C++

Memory: 7.85MB Beats51.63%of users with C++

 

class Solution {
public:
    string decodeString(string s) {

        vector<char> stack;
        for(auto c : s){
            if(c == ']'){
                vector<char> tmp_stack;
                while(stack.back() != '['){
                    // pop from stack and push into tmp_stack
                    tmp_stack.emplace_back(stack.back());
                    stack.erase(stack.end()-1);
                }
                // remove dummy '['
                stack.erase(stack.end()-1);
                // pop number from stack
                int digit = 0;
                int N = 0;
                while(stack.size() > 0 && stack.back() >= 48 && stack.back() <= 58){
                    N += (int(stack.back())-48) * (pow(10,digit++));
                    stack.erase(stack.end()-1);
                }
                cout << N << endl;
                // push substring in tmp_stack to stack N times
                for(int _ = 0; _ < N; ++_){
                    for(auto it = tmp_stack.end()-1; it >= tmp_stack.begin(); it--)
                        stack.emplace_back(*it);
                }
            } else {
                stack.emplace_back(c);
            }
        }

        return string(stack.begin(), stack.end());
    }
};