BOJ 2504 괄호의 값

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

2504번: 괄호의 값

결론부터 말하자면 첫 알고리즘은 실패했다.

 

#include <bits/stdc++.h>
#define Pair pair<char,int>
using namespace std;
int main() {
    int sum = 0;
    string s;
    stack<char> st;
    list<Pair> seq;
    cin >> s;
    for(int i=0;i<s.size();++i) {
        if(s[i] == '(' || s[i] == '[')
            st.push(s[i]);
        else { // 닫는 괄호
            char p = st.top()=='('?2:3;
            st.pop();
            seq.emplace_back(make_pair(p,st.size()));
        }
    }
    int n = seq.size();
    auto it = seq.begin();
    while(!seq.empty() && it!=seq.end()) {
        if (it->second == 0) {
            it = seq.erase(it);
            it++;
            continue;
        }
        int tmp = it->first;
        // auto itk = it; 인접한 두 원소(it2와 itk) 비교를 위해 아래 loop에서 itk라는 임시변수 이용 필요!
        for (auto it2 = it; it2 != seq.end();) {
            ++it2;
            if (it->second - it2->second == 1) {
                tmp *= it2->first;
                it2 = seq.erase(it2);
                // itk = it2
            }
            if (it2->second == 0) {
                break;
            }
        }
        sum += tmp;
        cout << tmp << endl;
        it++;
    }
    cout << sum;
}

 

스택은 괄호 취급 용도로, 실질 연산은 스택을 기반으로 만들어진 seq 리스트에서 이루어지는데, 

first: 괄호의 값, second: 스택에 남은 괄호의 개수가 저장된다. 여타 괄호를 이용한 stack 문제와 비슷하게 닫는 괄호가 나오면 top을 삭제한다.

 

second: 스택에 남은 괄호의 개수의 의미는 괄호 중첩으로 인해 x연산이 필요한 원소의 개수가 된다

 

이중 for loop에서 바깥 loop는 시작 위치, 안쪽 loop는 시작 위치의 다음 위치부터 seq 리스트를 순회하며, 인접한 두 원소들의 second가 순차적으로(1씩) 줄어드는 원소를 찾아 제거하고, first끼리 x연산을 수행한다.

 

e.g.

     [ ( [ ( ) ] ) ]

st: [([() -> seq: <2,3>

...

st: 0 -> seq: <2,3>, <3,2>, <2,1>, <3,0>

 

따라서 2*3*2*3 (-->) 순으로 곱셈이 이루어진다. 

 

 

* 다만 원소의 second가 0일때는 그 위치가 시작 위치로 가기 전까지는 지워서는 안된다.

  i.e 1 3 2 1 0 의 경우

  1 3 2 1 0 -> 1 3 2 1 0 -> 1 3 2 1 0 -> 1 3 2 1 0 의 과정이 필요하다.

 

사실상 1씩 줄어드는 Decreasing Subsequence를 찾아 삭제하는 문제로 바뀐다. 다만 문제는 구현이 조금 까다롭다는 것인데.. 리스트와 이터레이터에 익숙하지 않아 현재 코드로는 동작하지도 않으며, 수정이 필요하고, 시간복잡도 또한 개선의 여지가 있다.

 

알고리즘 자체가 틀린건 아닌것 같은데.. 보다 일반적인?풀이 방법으로 시도한 후 이터레이터를 공부한 후 다시 시도해볼 예정이다.