[백준 BOJ / C++] 2504번: 괄호의 값

 

문제링크: www.acmicpc.net/problem/2504

2504번: 괄호의 값

 

풀이

 

분배 법칙을 사용해서 문제를 풀 수 있다. ( ( ) [ [ ] ] ) 의 경우에 2x(2+3x3)으로 계산되는데, 이는 결국 (2x2) + (2x3x3)과 같다. 왼쪽 괄호가 나오면 temp에 2나 3을 곱한 뒤 스택에 push 하고, 오른쪽 괄호가 나오면 temp를 2나 3으로 나눈 뒤 스택을 pop 한다. 이때 ( ( ) [ [ ] ] ) 표시된 괄호처럼 괄호 값이 '( )' 또는 '[ ]'일 경우에는 temp 값을 나눠주기 전에 answer에 더한다. 

 

temp: answer에 더하기 전 중간값을 계산하기 위한 변수 (initial value: 1)

 

1. case ' ( '

   temp에 2를 곱하고 스택에 ' ( ' 를 push

 

 

2. case ' ) '

   1) 스택이 비어있거나 스택 top이 ' ( ' 가 아닌 경우

   올바르지 못한 괄호열이므로 answer = 0; break;

 

   2) 이전 문자열이 ' ( ' 일 경우

   괄호 값이 '( )' 이므로 계산된 temp 값을 answer에 더해주고 temp를 2로 나눈다. 스택을 pop 한다. 

 

   3) 이전 문자열이 ' ( ' 가 아닐 경우

   제일 안쪽 괄호, 즉 '( )' 형태가 아니므로 이미 answer에 값이 더해져 있는 상태이다. 따라서 answer에 값을 더하지 않고 temp를 2로 나누고 스택 pop을 한다. 

 

 

3, 4. case ' [ ', ' ] '

   1, 2와 유사하게 처리한다. 

 

마지막으로 만약 문자열을 다 읽었는데 스택이 비어있지 않다면, 올바르지 못한 괄호열이므로 answer = 0을 대입한다. 

 

 

 

 

소스코드

 

//2504 괄호의 값
#include <iostream>
#include <string>
#include <stack>
 
using namespace std;
 
string str;
stack<char> s;
 
int main(void) {
    cin >> str;
 
    int answer = 0, temp = 1;
    for(int i = 0; i < str.length(); i++) {
        if(str[i] == '(') {
            temp *= 2;
            s.push('(');
        }
        else if(str[i] == '[') {
            temp *= 3;
            s.push('[');
        }
        else if(str[i] == ')') {
            if(s.empty() || s.top() != '(') {   //올바르지 못한 괄호열
                answer = 0;
                break;
            }
            if(str[i-1] == '(') {
                answer += temp;
                temp /= 2;
                s.pop();
            }
            else {
                temp /= 2;
                s.pop();
            }
        }
        else if(str[i] == ']') {
            if(s.empty() || s.top() != '[') {   //올바르지 못한 괄호열
                answer = 0;
                break;
            }
            if(str[i-1] == '[') {
                answer += temp;
                temp /= 3;
                s.pop();
            }
            else {
                temp /= 3;
                s.pop();
            }
        }
    }
 
    if(!s.empty()) answer = 0;  //올바르지 못한 괄호열
 
    cout << answer << "\n";
 
    return 0;
}

 

 

 

공부한 것을 정리한 내용입니다. 수정할 부분이 있다면 알려주시면 감사하겠습니다 :)