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

작성일 | In |

Problem : 괄호의 값

유형 : 스택

문제 해석

  • 괄호열을 읽고 주어진대로 계산하여 결과를 출력하라.
  • 괄호안에 괄호가 있으면 곱 연산이 된다.
  • 그 외의 경우에는 합 연산이 된다.

해결전략

  • 관심을 가지고 보아야 하는점은 크게 3가지다
    • 올바른 괄호열인가?
    • 괄호 밖에 괄호가 있는가?
    • 괄호 안에 괄호가 있는가?
  • 스택을 이용하여 해결한다.
    • { 여는 괄호의 종류, 내부의 값 } 을 스택에 넣어 관리한다.
    • 내부의 값 이 존재한다면, 해당 여는 괄호 안에 다른 괄호가 존재했음을 나타나게 한다.

구현

  • 올바른 괄호열인지 판별한다.

  • 닫을때, 여는 괄호열이 정확히 있는지 확인한다.

  • 괄호 안에 괄호가 있는지 확인한다.
    • 기본적으로, 여는 괄호는 0 의 내부값을 가지고 있게 설정한다.
    • 괄호를 닫는 경우, 짝을 이루는 여는 괄호의 값이 0 이라면, 내부에 아무런 괄호가 없었다는 것이다.
      • 임시 변수에 2나 3을 더해준다.
    • 여는 괄호의 값에 0 이 아니라면, 내부에 괄호가 있었다는 것이다.
      • 임시 변수에 2나 3을 곱해준다.
  • 괄호 밖에 자신을 감싸는 괄호가 있는지 확인한다.
    • emtpy로 확인한다.
    • 스택안에 다른 여는 괄호가 있다면, 자신을 감싸는 괄호가 있다는 것이다. * 없다면, 전체값에 더해준다. * 있다면, 스택의 top 괄호에 임시 변수값을 더해준다.
  • 여는 괄호의 경우에는 { 괄호, 0 } 을 넣어준다.

코드

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
47
48
49
50
51
52
53
#include <bits/stdc++.h>
#define pii pair<char,int>
#define bracket first
#define insideValue second

using namespace std;

string str;

int solve() {
    cin >> str;
    stack<pii> s;

    int answer = 0;
    for (const char &c : str) {
        int tmp = 0;

        if (c == ')') {
            if (s.empty() or s.top().bracket != '(') return 0;

            if (s.top().insideValue == 0) tmp = 2;  // 괄호안에 다른 괄호가 없는 경우.
            else tmp = s.top().insideValue * 2;
            
            s.pop();
            if (s.empty()) answer += tmp;   // 괄호를 감싸는 다른 괄호가 없는 경우
            else s.top().insideValue += tmp;
        }
        else if (c == ']') {
            if (s.empty() or s.top().bracket != '[') return 0;

            if (s.top().insideValue == 0) tmp = 3;
            else tmp = s.top().insideValue * 3;

            s.pop();
            if (s.empty()) answer += tmp;
            else s.top().insideValue += tmp;
        }
        else s.push({ c, 0 });
    }
    return answer;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    cout << solve();

    return 0;
}

피드백

  • 과거 분명 풀었던 문제이지만, 솔루션을 떠올리기까지 시간이 좀 걸렸다.
  • 관심을 가져야 하는 데이터가 무엇인지,확실히 구별하고, 그 데이터를 어디에 저장하고 어떻게 사용할지에 대한 연습이 필요 해보인다.