압축 (1662번)

K(Q) : K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이다.

압축된 문자열 S가 들어오면 압축 풀어서 나온 문자열의 길이 출력하는 문제

33(562(71(9))) ⇒ 19

3567979567979567979

괄호 나오는 문자열이 나오면 일반적으로 스택 문제이다.

이 문제 스택 또는 재귀로 풀 수 있다.

재귀

#include<iostream>
#include<string>
using namespace std;

bool Visited[51];

string Str;

int DFS(int Index) 
{
    int Cnt = 0;

    for (int i = Index; i < Str.size(); ++i)
    {
        if (Str[i] == '(' && !Visited[i]) 
        {
            Visited[i] = true;
            int num = Str[i - 1] - '0';
            Cnt--; // 얘는 압축 숫자니깐
            Cnt += num * DFS(i + 1);
        }
        else if (Str[i] == ')' && !Visited[i]) 
        {
            Visited[i] = true;
            return Cnt;
        }
        else if (!Visited[i]) 
        {
            Visited[i] = true;
            Cnt++;
        }
    }

    return Cnt;
}

int main() 
{
    ios::sync_with_stdio(false), cin.tie(0);

    cin >> Str;

    cout << DFS(0);

    return 0;
}

스택

#include<iostream>
#include<string>
#include<stack>
using namespace std;

string Str;

int main() 
{
    ios::sync_with_stdio(false), cin.tie(0);

    cin >> Str;
    
    stack<int> Stack;
    for (int i = 0; i < Str.size(); i++) 
    {
        if (Str[i] == '(') Stack.push(-1);
        else if ('0' <= Str[i] && Str[i] <= '9')
        {
            if (i < Str.size() - 1 && Str[i + 1] == '(')
            {
                Stack.push(Str[i] - '0');
            }
            else Stack.push(1);
        }
        else 
        {
            int Length = 0;
            while (Stack.top() != -1) 
            {
                Length += Stack.top();
                Stack.pop();
            }
            Stack.pop();
            Length *= Stack.top();
            Stack.pop();
            Stack.push(Length);
        }
    }
    int Answer = 0;
    while (!Stack.empty()) {
        Answer += Stack.top();
        Stack.pop();
    }

    cout << Answer;

    return 0;
}