[백준 1662] 압축

문제

https://www.acmicpc.net/problem/1662

 

알고리즘

재귀

 

풀이

압축된 문자열이 주어졌을 때, 원래 문자열의 길이를 구하는 문제입니다.

 

재귀적인 시각으로 문제를 바라보면 이해하기 쉽습니다. $abcd(efg(hi))$ 와 같이 문자열이 주어졌다면 그대로 보기보다는 $abcd(*)$ 와 같이 이해를 해봅시다. 문제에서 주어진 문자열을 해결하는 함수 $solve()$가 있다면 우리는 $abc$ 길이에 $d$ X $solve(*)$ 와 같이 문제를 나눌 수 있습니다. $solve()$ 함수 내에서 또 다른 $solve()$를 호출하여 재귀적으로 해결하도록 합시다.

 

이 문제에서 생각해야할 부분은 괄호를 제외한 *에 해당하는 문자열을 인자로 넘겨주는 방법입니다. 올바른 괄호 문자열 문제처럼 여는 괄호라면 +1, 닫는 괄호라면 -1로 카운트하여 총 합이 0이 된다면 올바른 괄호 문자열 입니다. 문자열을 처리하는 중 여는 괄호를 만났다면 이 방법을 사용해 현재 여는 괄호와 상응하는 닫는 괄호를 찾아 $substr()$함수를 통해 인자로 넘겨주면 됩니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

string S;

int solve(string s) {

    int ans = 0;
    stack<char> stk;
    for (int i = 0; i < s.length(); ++i) {
        if (s[i] != '(') {
            stk.emplace(s[i]);
        } else {
            int cnt = 0;
            int tempI = i;

            while (1) {
                char x = s[tempI];
                if (x == '(') ++cnt;
                else if (x == ')')
                    --cnt;
                if (cnt == 0) break;
                ++tempI;
            }

            int reputation = stk.top() - '0';
            stk.pop();
            int ret = solve(s.substr(i + 1, tempI - i - 1));
            ans += reputation * ret;
            i = tempI;
        }
    }
    while (!stk.empty()) {
        stk.pop();
        ++ans;
    }
    return ans;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> S;
    cout << solve(S);
    return 0;
}