[백준 - 2504] 괄호의 값 - C++

분류: 스택, 재귀 /

 

문제

문제 링크

문제 설명

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.

1. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.
2. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다.
3. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.

예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다.

1. ‘()’ 인 괄호열의 값은 2이다.
2. ‘[]’ 인 괄호열의 값은 3이다.
3. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
4. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.

예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.

여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다.

입력

첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.

출력

첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다.

 

풀이

- 스택

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

struct e { char c; int v; };
map<char, e> m{ {')', {'(', 2}}, {']', {'[', 3}} };

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

    string s; cin >> s;
    int ans = 0;
    stack<e> st;
    for(char c:s) {
        if(m.find(c) != m.end()) st.push({c, 0});
        else {
            if(st.empty()) { ans = 0; break; }

            int v = st.top().v;
            if(m[c].c != st.top().c) { ans = 0; break; }
            v = v ? v * m[c].v : m[c].v;
            st.pop();
            
            if(st.empty()) ans += v;
            else st.top().v += v;
        }
    }
    cout << ans;
}

아래와 같은 풀이다.

 

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

struct e { char c; int v; };

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

    string s; cin >> s;
    int ans = 0;
    stack<e> st;
    for(char c:s) {
        if(c == '(' || c == '[') st.push({c, 0});
        else {
            if(st.empty()) {
                ans = 0; 
                break;
            }

            int v = st.top().v;
            if(c == ')'){
                if(st.top().c != '(') {
                    ans = 0; 
                    break;
                }
                if(v == 0) v = 2;
                else v *= 2;
            } else if(c == ']'){
                if(st.top().c != '[') {
                    ans = 0; 
                    break;
                }
                if(v == 0) v = 3;
                else v *= 3;
            }

            st.pop();
            
            // trace back
            if(st.empty()) ans += v; // top level
            else st.top().v += v; // outer level
        }
    }
    cout << ans;
}

문제를 보고 처음 든 생각은 재귀로 풀면 될 거 같은데?

괄호의 모양과 상황마다 처리하는 로직이 달라지므로 재귀호출의 앞에서 분기하고 재귀호출 뒤에서 분기에 맞춰 계산해 주면 될 거 같다는 생각이 들었다. 재귀로는 할 수 있을 거 같으니 재귀를 안 쓰고 풀어보자!

 

문제에서 까다로운 부분은 언제 더하고 언제 곱하느냐이다. 소괄호 대괄호는 그냥 분기로 처리하면 그만.

괄호가 열릴 때마다 상태가 생긴다. 그래서 처음에 재귀를 떠올렸다. 루프마다 상태를 가져야 하니.

재귀를 안 쓰고 어떻게 루프마다 상태를 갖고 trace 하며 상태를 누적할까 생각해 보니 구조체를 만들어 스택에 상태를 저장하면 된다.

 

스택에는 여는 괄호만 저장된다. 괄호가 열릴 때 상태를 생성하고 괄호가 닫힐 때 상태를 회수한다. 괄호를 재귀함수 렉시컬 환경이라고 보면 된다.

괄호가 모두 회수되면 (top level에 도달하면) `ans`에 더해주고 아직 스택에 괄호가 있다면 outer level에 결과를 누적한다.

괄호 안의 계산 값들은 왼쪽 여는 괄호에 쌓이고 괄호가 닫히면서 쌓인 값들에 곱하기를 한다.

 

괄호가 닫힐 때도 분기처리 해주어야 하는데 괄호가 바로 닫히는 경우(더하기)와 다른 괄호를 포함하고 닫히는 경우(곱하기)다.

- 재귀

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

map<char, char> pairMap{{']', '['}, {')', '('}};
map<char, int> pointMap{{']', 3}, {')', 2}};

int getPoint(string& s){
    char c = s.back();
    if(pairMap.find(c) == pairMap.end()) return -1;
    s.pop_back();
    if(s.empty()) return -1;

    int point = 0;
    while(s.back() != pairMap[c]) {
        int p = getPoint(s);
        if(p < 0 || s.empty()) return -1;
        point += p;
    }
    s.pop_back();

    if(point == 0) return pointMap[c];
    return pointMap[c] * point;
}

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

    string s; cin >> s;
    
    int ans = 0;
    while(s.length() > 0) {
        int point = getPoint(s);
        if(point < 0) {
            ans = 0;
            break;
        }
        ans += point;
    }
    cout << ans;
}

덧셈을 while문으로 처리해 줬다.

`getPoint` 함수는 항상 2개의 씩 pop 한다. 그렇지 못할 경우 실패(-1)

`getPoint` 마지막에 `point`가 0이라는 뜻은 while문을 거치지 않았다는 뜻이다. 즉 `()`혹은 `[]`이다.

while문을 거쳤다면 `point`에는 괄호 사이에 점수의 합이 저장되어 있고 `c`로 시작되는 괄호를 끝낸다.

 

입력된 문자열 자체를 스택으로 사용하기 위해 문자열 뒤에서부터 시작한다. 따라서 hash table도 닫히는 괄호기 키다.

if 문을 줄이고 싶어서 `map`을 썼다.

 

- 다른 사람 풀이

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

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

    string str; cin >> str;
    stack<char> S;
    int ans = 0, val = 1;
    for(int i=0, len=str.length(); i<len; i++) {
        char c = str[i];
        if(c == '(') {
            S.push(c);
            val *= 2;
        }
        else if(c == '[') {
            S.push(c);
            val *= 3;
        }
        else if(c == ')') {
            if(S.empty() || S.top() != '(') {
                ans = 0;
                break;
            }
            if(str[i-1] == '(') ans += val;
            S.pop();
            val /= 2;
        }
        else if(c == ']') {
            if(S.empty() || S.top() != '[') {
                ans = 0;
                break;
            }
            if(str[i-1] == '[') ans += val;
            S.pop();
            val /= 3;
        }
    }
    if(S.empty()) cout << ans;
    else cout << 0;
}

`(()[[]]) = (()) + ([[]])` 분배법칙을 이용한 풀이다.

값은 depth에 따라 결정되며 괄호를 열 때 곱하고 닫을 때 나누어 depth를 조절한다.

옳은 괄호열이라면 `()` 혹은 `[]`처럼 붙어 있는 쌍의 개수로 분배법칙을 이용해 쪼갤 수 있다. 각각의 depth에서 더해주면 된다.