백준 2504번 괄호의 값

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

2504번: 괄호의 값

 

문제

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을 출력해야 한다. 

 

풀이

스택 문제입니다!

 

이 문제에서는 두 가지를 한꺼번에 해줘야 하는 어려움이 있다.

 

1. 올바른 괄호열인지 확인

2. 괄호값 계산

 

따라서, 두 가지를 동시에 처리하지 않고, 각각을 다른 stack으로 처리해주는 게 좋다.

 

1. 올바른 괄호열은 열린 괄호일 때 stack에 넣고, 닫힌 괄호가 나왔을 때 stack의 top이 그 와 짝이 맞는지 확인한다.

2. 괄호값 계산도 stack으로 처리할 수 있는데, 왜냐하면 바깥쪽 괄호값은 안쪽 괄호값에 대한 곱이기 때문이다.

 

괄호값 stack 처리는 코드를 보고, 밑에서 설명하도록 하겠다.

 

소스 코드

#include <iostream>
#include <stack>
#include <string>
using namespace std;
 
int main()
{
    string s; cin >> s;
 
    stack<char> st; //괄호 stack
    stack<int> value; //괄호값 stack
 
    int ans = 0; //완성된 괄호값
    int part_ans = 0; //아직 미완성 괄호값
    
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(' || s[i] == '[') {
            st.push(s[i]);
            value.push(0); //여는 괄호는 0을 push
        }
        //닫힌 괄호일 때 조건이 많음
        else {
            if (st.empty()) { //올바르지 못한 괄호열 처리
                printf("0");
                return 0;
            }
            else if (s[i] == ')') {
                if (st.top() != '(') { //올바르지 못한 괄호열
                    printf("0");
                    return 0;
                }
                else {
                    part_ans = value.top();
                    value.pop();
                    if (part_ans == 0) part_ans = 1;
                    part_ans *= 2;
                    if (value.empty()) ans += part_ans;
                    else {
                        part_ans += value.top();
                        value.pop();
                        value.push(part_ans);
                    }
                }
                st.pop();
            }
            else if (s[i] == ']') {
                if (st.top() != '[') { //올바르지 못한 괄호열
                    printf("0");
                    return 0;
                }
                else {
                    part_ans = value.top();
                    value.pop();
                    if (part_ans == 0) part_ans = 1;
                    part_ans *= 3;
                    if (value.empty()) ans += part_ans;
                    else {
                        part_ans += value.top();
                        value.pop();
                        value.push(part_ans);
                    }
                }
                st.pop();
            }
        }
    }
    if (!st.empty()) ans = 0;
    printf("%d", ans);
    return 0;
}

우선, 주석 처리한 부분이 1번 올바르지 않은 괄호열 처리에 해당하고,

 

 

else {
        part_ans = value.top();
        value.pop();
        if (part_ans == 0) part_ans = 1;
        part_ans *= 2;
        if (value.empty()) ans += part_ans;
        else {
            part_ans += value.top();
            value.pop();
            value.push(part_ans);
        }
    }

바로 이 부분이 괄호값을 stack으로 표현한 부분이다.

 

과정을 살펴보면

• 열린 괄호일 때 0을 stack에 push
• 닫힌 괄호가 나오면, part_ans을 stack의 top으로 초기화 후 stack을 pop
• 만약 맨 위가 열린괄호였다면, 2로 초기화
• 만약 stack이 비어있다면 정답에 추가
• 비어있지 않다면, part_ans에 stack의 top을 더하고, pop 후 part_ans를 push

첫 단계부터 설명하자면,

열린 괄호일 때 0을 넣는 이유는 ( ( ) ( ) ) 같은 경우 3번째 index의 닫힌 괄호를 처리할 때 

만약 열린괄호를 1로 넣어버리면 part_ans가 밑에서 +1 더해지기 때문에 변동이 없게하기 위해 0을 넣는다.

 

닫힌 괄호가 나오면, 이미 만들어진 괄호값 stack에 2를 곱하고, 만약 5번째 index를 처리할 때 이미 stack 밑에 2가 있기 때문에 2를 더해줘야 하기 때문에 top을 더하고 pop하고 5를 push한다.

 

만약 stack이 비어있다면, 더 이상 안에 처리할 괄호열이 없기 때문에 2를 곱해서 정답에 더해준다.

 

이런 과정은 글로 된 설명보다 직접 그려서 이해하는 게 더 빠른 것 같다.

 

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~