엘리스 코드 챌린지 Day 3 문자열 압축 해제

문제

 

풀이

괄호 안에 존재하는 수를 괄호 바로 앞에 있는 수만큼 반복한 문자열로 만들 수 있고, 모든 괄호를 제거했을 때 문자열의 길이를 구하는 문제입니다.

처음에는 재귀를 통해서 문자열을 직접 구해서 해결했었는데

어떤분께서 게시글에 int 범위가 벗어난다는 의견을 제시해주셔서 다시 풀게 되었습니다. 아마 저는 틀렸겠지요... ㅠ

 

생각해보니 문자열을 직접 구할 필요가 없더라고요! 길이만 구하면 되니까요!

그래서 이번에는 스택으로 접근했습니다.

문제의 핵심은 괄호 안의 숫자를 k번 반복한다는 것입니다.

그러면 괄호 안의 숫자의 길이 * k가 스택에 들어가면 된다는거겠죠.

 

그러면 스택에는 숫자와 괄호를 구분할 필요가 생깁니다.

우선 숫자가 나온다면 다음 문자가 "(" 인지 확인해야 합니다.

다음 문자가 "("가 아니라면 스택에 1을 넣으시면 됩니다. (길이가 1인 문자열)

다음 문자가 "("이라면 반복에 활용되는 k에 해당되기 때문에 해당 숫자를 스택에 넣습니다.

 

다음은 괄호가 나왔을 경우입니다.

현재 위치가 "("이면 괄호 구분을 위해 스택에 -1을 넣습니다.

스택에는 양의 정수만 들어가기 때문에 이런 방식으로 숫자와 괄호를 구분할 수 있습니다.

 

현재 위치가 ")"이면 스택에 쌓여있는 문자열의 길이들을 더해주도록 합니다.

괄호 짝인 -1이 나올 때까지만 더해주시면 됩니다.

그리고 -1 바로 다음에 있는 수를 꺼내서 곱한 값을 스택에 다시 넣어줍니다.

그러면 3(8) = 888의 과정이 마무리된 것입니다.

-1이 열리는 괄호가 되겠고, 바로 다음에 있는 수가 3에 해당됩니다. 8은 당연히 -1이 나오기 전까지 더한 값들이 됩니다.

 

위 과정들이 모두 끝난다면 스택에는 문자열의 길이가 여러개 들어있을 것입니다.

그 숫자들을 모두 더해주시면 답을 구할 수 있습니다.

문제에는 수의 범위가 명시되어있지 않기 때문에 lnog long 자료형으로 출력해주도록 합니다.

 

코드

#include <iostream>
#include <string>
#include <stack>
using namespace std;
typedef long long ll;
 
string str;
int N;
 
void func() {
    stack<ll> s;
    for (int i = 0; i < N; i++) {
        if (str[i] == '(') {
            s.push(-1);
        }
        else if (str[i] == ')') {
            ll sum = 0;
            while (1) {
                ll x = s.top();
                s.pop();
                if (x == -1) break;
                sum += x;
            }
            ll tmp = s.top();
            s.pop();
            s.push(tmp * sum);
        }
        else if (i < N - 1 && str[i + 1] == '(') {
            s.push((ll)(str[i] - '0'));
        }
        else s.push(1LL);
    }
 
    ll ret = 0;
    while (!s.empty()) {
        ret += s.top();
        s.pop();
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> str;
    N = str.size();
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}