엘리스 코드 챌린지 Day 3

code-challenge.elice.io

 

엘리스 코드 챌린지 Day 3에는 '문자열 압축 해제'라는 문제가 나왔습니다.

Day 1, 2에 비해 갑자기 어려워져서 놀랐습니다.

 

괄호가 포함된 문자열을 해석할 때는 스택(stack) 자료구조와 재귀적인 접근을 이용하는 것이 좋습니다.

 

문제를 풀기 전, 괄호 문자열에 대해 여는 괄호는 닫는 괄호 짝의 인덱스를, 닫는 괄호는 여는 괄호 짝의 인덱스를 빠르게 찾을 수 있도록 스택을 이용하여 opened[N], closed[N] 배열에 기록해둡시다.

 

문제를 해결하기 위해 문자열 $S$에 대해 $\mathrm{solve}(S)$를 정의합시다.

이때, 문자열 $S$는:

• 첫 번째 문자가 숫자여야 하고,
• 괄호로 이루어진 부분수열(subsequence)이 올바른 괄호 문자열을 이룬다고 전제합니다.

$S$의 모든 $K(Q)$꼴의 부분문자열(substring)에 대해, 해당 부분의 값은 $K \times \mathrm{solve}(Q)$입니다.

이러한 부분문자열들을 제외한 숫자들은 각각 $1$의 값을 갖습니다.

이 값들을 전부 더하면 $\mathrm{solve}(S)$의 값을 올바르게 구할 수 있습니다.

 

#include <bits/stdc++.h>
using namespace std;

const int N = 53;
int n;
string s;
int opened[N];
int closed[N];

int64_t solve(int l, int r) {
    if (l>r) return 0;
    int64_t res = 0;
    for (int i = l; i <= r; ++i) {
        if (s[i+1] == '(') {
            res += (s[i]-'0') * solve(i+2, closed[i+1]-1);
            i = closed[i+1];
        } else {
            res++;
        }
    }
    // cout << "solve(\"" << s.substr(l,r-l+1) << "\")=" << res << endl;
    return res;
}

int main() {
    cin >> s;
    n = size(s);
    s = "$"+s;
    stack<int> S;
    for (int i = 1; i <= n; ++i) {
        if (s[i]=='(') S.push(i);
        else if (s[i]==')') {
            opened[i]=S.top();
            closed[S.top()]=i;
            S.pop();
        }
    }
    cout << solve(1,n);
}