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

---

0. 문제

 

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

1. 아이디어

 

1) 기본적으로 수학에서의 '분배법칙' 의 아이디어를 차용한다.

 

2) 임시로 값을 저장할 temp와, 순간의 temp들을 더해서 최종값을 나타낼 result 변수를 선언한다.

 

3) '('나 '['를 만나면 각각 temp에 2와 3을 곱한 후 스택에다가 PUSH 해준다.

 

4) ')'와 ']'를 만나서 괄호가 정상적으로 닫히게 되면, temp에 저장된 값을 result에 더해주고 temp의 값을 각각 다시 2와 3으로 나눠준다.

(이 때, 스택의 TOP()을 보고, 괄호가 짝이 지어지면 정상적으로 닫히게 됨)

 

5) 정상적인 괄호가 아닌 경우에는 0을 출력한다.

 

2. 소스코드

 

 #include <iostream>
#include <stdlib.h>
#include <stack>
int main()
{
    int temp = 1, result = 0;
    std::string str;
    std::cin >> str;
    std::stack<char> st;
 
    for (int i = 0; i != str.length(); i++)
    {
        if (str[i] == '(')
        {
            temp *= 2;
            st.push('(');
        }
        else if (str[i] == '[')
        {
            temp *= 3;
            st.push('[');
        }
        else if (str[i] == ')')
        {
            if (st.empty()) {
                std::cout << "0"; exit(0);
            }
            else if (str[i - 1] == '(')
            {
                result += temp;
                temp = temp / 2;
                st.pop();
            }
            else if (st.top() == '(')
            {
                st.pop();
                temp = temp / 2;
            }
            else
            {
                std::cout << "0";
                exit(0);
            }
        }
        else if (str[i] == ']')
        {
            if (st.empty()) {
                std::cout << "0";
                exit(0);
            }
            else if (str[i - 1] == '[')
            {
                result += temp;
                temp = temp / 3;
                st.pop();
            }
            else if (st.top() == '[')
            {
                st.pop();
                temp = temp / 3;
            }
            else  
            {
                std::cout << "0";
                exit(0);
            }
        }
    }
    if (st.empty()) std::cout << result; //여기서 st.empty()는 모든 괄호들이 짝을 지었는지를 판단
    else std::cout << "0";

 

3. 결과

 

 

4. 피드백

 

• 만만하게 보고 덤볐다가 결국 풀이보면서 공부함..
• 닫는 괄호가 나올 때, 스택이 비어있는 예외를 생각 못했다.
• 닫는 괄호는, 여는 괄호가 바로 앞에 나왔을 때만 값을 더해줘야 한다. (스택이 아니라 문자열에서!)
• 여는 괄호와 닫는 괄호의 개수는 같아야 한다! (최종적으로 스택은 비어있어야 한다)
• 프로그램은 반드시 0을 리턴해야 한다. 아니면 런타임에러! exit(1)로 끝내려다가 계속 런타임에러..

---