BOJ/백준 2504 괄호의 값

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

 

 

문제 해결 아이디어

주어진 예시인

(()[[]])([])

로 봤을때

2 * (2 + 3 * 3) + (2 * 3)인데

이것을 풀어 쓰면

(2 * 2) + (2 * 3 * 3) + (2 * 3) 이다

이 아이디어를 바탕으로 스택을 활용해 문제를 해결 할 수 있다.

 

코드

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    string str;
    stack<char> s;
    int tmp = 1, ans = 0, len;
    cin >> str;

    len = str.length();

    for(int i = 0; i < len; i++){
        if(str[i] == '('){
            s.push(str[i]);
            tmp *= 2;
        }
        else if(str[i] == '['){
            s.push(str[i]);
            tmp *= 3;
        }
        else{
            if(str[i] == ')'){
                if(s.empty() || s.top() != '('){
                    ans = 0;
                    break;
                }
                if(str[i - 1] == '(') ans += tmp;
                s.pop();
                tmp /= 2;
            }
            else if(str[i] == ']'){
                if(s.empty() || s.top() != '['){
                    ans = 0;
                    break;
                }
                if(str[i - 1] == '[') ans += tmp;
                s.pop();
                tmp /= 3;
            }
        }
    }
    if(!s.empty()) ans = 0;
    cout << ans;
    return 0;
}

 

설명을 하자면

(()[[]])

우선 이 부분만 봤을때 

2 * (2 + 3 * 3) 이고 (2 * 2) + (2 * 3 * 3) 이렇게 풀어 쓸 수 있다

우리가 볼 것 은 후자이다

 

먼저 '('로 괄호가 열릴때 2를 곱해주고 2번째로 괄호가 열릴때 또 2를 곱해준다 그러면

ans = (2 * 2)가 완성 되는 것이다. 이때 현재 tmp 값을 4이니 다음 계산을 위해 3을 나눠서 tmp 값을 2로 만들어 준다

 

그 다음 '['을 만날때 2 * 3 = 6으로 만들어주고 또 그 다음 '['을 만날때 6 * 3 을해서 18을 만들어 준다

그리고 이때 ']'을 만날때 ans += tmp 를 해줘서 (2 * 2) + (2 * 3 * 3)을 완성 한다. 그리고 tmp /= 3 을 해서 6으로 만들어 준다

 

그 다음 ']' 를 만날 때에는 str[i - 1] == '[' 이 조건에 맞지 않아고 ans += tmp이 실행 되지 않고 tmp /= 3을 해서 2로 만들어 준다

또 그 다음 ')'으로 괄호를 완전히 닫아 주면 tmp /= 2 가 실행되어 tmp는 1이 된다.

 

이 문제를 풀면서 느꼇는게 보통 전의 값을 확인할때 s.top()를 이용해 값을 확인 했었는데 s.top() 올바는 괄호인지 체크만 하고

값을 넣는 조건은 str[i - 1] 을 이용해 바로 직전 값이 여는 괄호인지 체크한다는 것이 문제를 푸는데 많은 시간이 들게 되었다.