[Stack][Medium] 394. Decode String

https://leetcode.com/problems/decode-string/description

Decode String - LeetCode

 

Q. k[string] 꼴의 입력이 들어올때, string을 k번 출력하게 디코딩 하라.

 

Solution. 

  전형적인 stack을 활용해야 하는 문제 중의 하나다. 

  이런 유형의 문제를 풀 때 유의해야 할 점은, 도중 산출 과정을 그대로 main stack에 반영해야 이후 연산에 자동으로 누적 적용 된다는 것이다. 

   즉, 특정 string을 별도 캐시에 저장하거나 하기 시작하면, 복잡도가 불필요하게 매우 증가하게 된다. 

   따라서 최대한 메인 버퍼에 과정을 지속 기록하면서 디코딩 해 나가는 것이 문제 풀이의 핵심이라 하겠다. 

 

 Medium 혹은 조금 더 상위 난위도의 문제.

 

C++

string decodeString(string s)
{
    stack<char> sBuff;
    for (int k = 0; k < s.size(); ++k)
    {
        char cur = s[k];
        if (cur == ']')			// 닫힘 문자를 만났을때 필요 연산 수행.
        {
            string src = "";
            string num = "";
            while (true)		
            {
                if (sBuff.empty())
                    break;
                else
                {
                    // 스택을 역순회 하며 필요한 정보를 만든다.
                    char last = sBuff.top();
                    if (last >= '0' && last <= '9')
                    {
                        num += last;
                        sBuff.pop();
                    }
                    else
                    {
                        if (num.size() > 0)
                            break;
                        else
                        {
                            src = last!='[' ? src + last : src;
                            sBuff.pop();
                        }
                    }
                }
            }

            // 얻은 정보로 stack에 문자를 디코딩한다.
            reverse(num.begin(), num.end());
            int times = num.size()>0 ? atoi(num.c_str()) : 0;

            reverse(src.begin(), src.end());
            for (int z = 0; z < times; ++z)
            {
                for (int q = 0; q < src.size(); ++q)
                    sBuff.push(src[q]);
            }
        }
        else sBuff.push(cur);
    }

    // 스택에서 char를 꺼내 string 변환한다.
    string ret = "";
    while (!sBuff.empty())
    {
        ret += sBuff.top();
        sBuff.pop();
    }
    reverse(ret.begin(), ret.end());
    return ret;
}

 

 

C#

public string DecodeString(string s) 
{
    Stack<char> stBuff = new Stack<char>();

    for(int q = 0; q < s.Length; ++q)
    {
        char cur = s[q];
        if(cur == ']')
        {
            string src = "";
            while(stBuff.Peek() != '[')
                src += stBuff.Pop();
            src = new string( src.Reverse().ToArray() );

            stBuff.Pop();   // [

            string num = "";
            while(stBuff.Count>0 && stBuff.Peek()>='0' && stBuff.Peek()<='9')
                num += stBuff.Pop();

            num = new string(num.Reverse().ToArray());
            int count = int.Parse(num);

            for(int z = 0; z < count; ++z)
            {
                for(int k = 0; k < src.Length; ++k)
                    stBuff.Push(src[k]);
            }
        }
        else 
            stBuff.Push(cur);
    }

    string ret = "";
    while(stBuff.Count > 0 ) 
        ret += stBuff.Pop();

    return new string( ret.Reverse().ToArray() );
}

 

 

 

Outcome