[leetcode 394] Decode String

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].

 

[]안에 문자열을 k번 반복한 새로운 문자열을 출력한다.

 

Example 1:

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

Example 2:

Input: s = "3[a2[c]]" Output: "accaccacc"

Example 3:

Input: s = "2[abc]3[cd]ef" Output: "abcabccdcdcdef"

Example 4:

Input: s = "abc3[cd]xyz" Output: "abccdcdcdxyz"

 

풀이:

- 스택 사용

- 코테에 비스무리한 문제가 자주 나왔던 거 같은데 이번 기회에 정리하면 좋을 듯 하다.

- isdigit, stoi 알아둘것

- string보다는 char을 저장하는게 쉽다.

- 원리: ]가 아닌이상 다 stack에 저장하고 ]가 등장하면 [까지 pop해서 문자열을 추출 -> 그 다음에 숫자를 추출. 다시 스택에 푸쉬

- 문자열 추출시 주의사항: stack엔 거꾸로 저장되어 있기 때문에 top을 문자열 앞에 위치시켜야 한다. 기존문자열 = top + 기존문자열 순

class Solution {
public:
    string decodeString(string s) {
       string result="";
        
        stack<char> stk;
       for(int i=0; i<s.length(); i++){
           if(s[i]!=']'){
               stk.push(s[i]);
           }else {
               
               // []안에 있는 문자열 pop
               string encode = "";
               while(!stk.empty() && stk.top() != '['){
                   encode = stk.top() + encode;
                   stk.pop();
               }
               stk.pop(); //pop '['

				//앞에 붙은 숫자 pop
               string tmp = "";
               while(!stk.empty() && isdigit(stk.top())){
                   tmp = stk.top()+ tmp;
                   stk.pop();
               }
            
               int repeat = stoi(tmp);
               while(repeat--){
                  for(int j=0; j<encode.length(); j++){
                      stk.push(encode[j]); //다시 스택에 넣어줘야한다.
                  }
               }
           }
   
       }
        
        while(!stk.empty()){
            result = stk.top() + result;
            stk.pop();
        }
        return result;
    }
};