괄호의 값

작성일 | In

[백준] 2504번 - 괄호의 값

문제 링크

처음에는 후위계산식과 같은 기본적인 스택문제인줄 알았으나, 조금 더 열린 사고로 풀어야했던 문제이다.
괄호 쌍을 맞추기 위해 스택 자료구조를 이용했다. 괄호열을 순차적으로 탐색하며 열린 괄호는 스택에 저장하고, 닫힌 괄호를 만났을 때 가장 최근에 만난 열린 괄호와 쌍이 맞는지를 검사하는 과정은 여느 괄호 관련 문제와 다름이 없다.
다만 괄호들의 나열 상태에 따라 각 시점에서 어떤 연산을 해야 하는지 유추해야 하는 점이 어려웠고, 긴 고민 끝에 분배법칙을 이용하여 문제를 풀었다.

분배법칙 개념을 어떤 식으로 적용할 수 있는지 간단한 예시로 살펴보자.
괄호열로 “ (()[]) “ 가 주어졌다고 가정할 때, 이를 수식으로 치환하면 2 x (2 + 3) 이다.
이 수식은 2 x 5 로 표현할 수도 있고, 2x2 + 2x3 으로 표현할 수도 있다.
두 번째 표현법이 분배법칙을 이용한 수식이고, 필자는 이 방법으로 문제를 풀었다.

분배법칙을 적용하기 위해 코드에서 weight라는 변수를 사용했다. weight는 어떤 괄호가 완성되었을 때, 그 괄호의 값을 매길 때 사용된다.
조금 더 자세히 말해보자면, 닫힌 괄호를 만났을 때 해당 괄호에 대한 값을 판단하게 된다. 이 때 이 괄호가 몇 개의 소괄호 혹은 대괄호 쌍 내부에 존재하는지를 알려주는 지표가 weight변수의 역할이다.
위에서 든 예시를 통해 weight값이 어떻게 쓰이는지 살펴보자.

  • weight의 초기값은 1이다. 괄호열 “ (()[]) “ 의 1번째 괄호는 열린 괄호이므로 스택에 저장된다. 이 때 weight에 소괄호의 가중치인 2를 곱한다.
  • 2번째 괄호도 마찬가지로 스택에 저장 후 weight에 2를 곱한다. 이 시점에서 weight는 2x2=4인 상태이다.
  • 3번째 괄호는 닫힌 괄호이므로 스택의 top이 ‘(‘ 인지 확인한다. 맞다면 스택의 top을 제거한다. 그리고 바로 직전 괄호(여기서는 2번째 괄호)를 확인하여 괄호가 완성되는 타이밍인지를 확인한다. 2,3번째 괄호가 모여 하나의 완성된 괄호쌍을 이루기 때문에 이 때 weight 값을 계산 결과를 저장하는 result 변수에 더한다. 여기가 포인트인데, 하나의 괄호쌍이 완성된 시점에서는 해당 괄호쌍의 수치(소괄호쌍은 2, 대괄호쌍은 3)만큼 weight의 값을 줄여주어야 한다. 즉, weight에서 2를 나눈다.
  • 4번째 괄호는 열린 대괄호이므로 weight = weight * 3을 통해 weight는 6이 된다. 마찬가지로 열린 대괄호는 스택에 저장된다.
  • 5번째 괄호는 닫힌 대괄호이므로 스택의 top이 ‘[‘인지 확인하고, 스택의 top을 제거한다. 바로 직전 괄호가 열린 대괄호이므로 하나의 대괄호쌍이 완성된 시점임을 알 수 있다. 따라서 result = result + weight 연산을 수행한다.
  • 마지막 6번째 괄호는 닫힌 소괄호이고, 스택의 top이 ‘(‘이므로 스택의 top을 제거한다. 바로 직전의 괄호는 ‘]’이므로 하나의 괄호쌍이 완성되는 시점이 아님을 알 수 있다. 따라서 result에 더하는 연산은 수행하지 않는다.

계산 과정을 쭉 살펴보면 어떤 풀이 방식인지 조금은 감이 올 것이다. 순차적으로 괄호열을 탐색하면서 하나의 괄호쌍이 완성되는 시점에만 계산 결과 변수에 값을 더해주는 방식이라고 간단하게 표현할 수 있을 것 같다.
아래는 동일한 방법으로 문제를 푼 분의 블로그 설명글이다. 필자와는 달리(?) 굉장히 쉽고 가독성 좋게 설명하셨다. 한 번 읽어보기를 추천한다.
https://soobarkbar.tistory.com/151

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;

stack<char> stk;

int main(void) {
    char input[31];
    scanf("%s", input);
    string brackets = input;

    bool isWrong = false;
    int weight = 1;
    int result = 0;
    for(int i=0; i<brackets.length(); ++i) {
        char cur = brackets[i];
        if(cur == '(' || cur == '[') {
            weight *= cur == '(' ? 2 : 3;
            stk.push(cur);
        } else {
            // 닫힌 괄호를 만났는데 이전에 만난 열린 괄호가 없다면 잘못된 괄호열
            if(stk.empty()) {
                isWrong = true;
                break;
            }
            char before = stk.top();
            stk.pop();
            if((cur == ')' && before == '(') || (cur == ']' && before == '[')) {
                // 바로 직전 괄호를 살펴봄으로써 result에 더해야 하는지를 판단한다.
                if(brackets[i-1] == '(' || brackets[i-1] == '[')
                    result += weight;
                weight /= cur == ')' ? 2 : 3;
            } 
            // 괄호 쌍이 맞지 않으면 잘못된 괄호열
            else {
                isWrong = true;
                break;
            }
        }
    }

    // 열린 괄호가 남아있다면 잘못된 괄호열
    if(isWrong || !stk.empty())
        printf("0");
    else
        printf("%d", result);
}
0%