[BaekJoon] 2504번 - 괄호의 값 [Java][C++]

문제 링크

---

1. 아이디어

올바른 괄호열인지 여부와 올바른 괄호열이면 괄호값을 출력해야 하는 문제로 괄호 문제다 보니 스택을 사용하면 되며 덧셈과 곱셈의 분배 법칙을 활용해서 해결했다.

산술에서 $(A + B) \times C = A \times C + B \times C$ 로 곱셈을 분배해줄 수 있는데, 이를 올바른 괄호열 계산에도 동일하게 적용해서 (()[[]])([])의 괄호값은 (())와 ([[]])와 ([])의 괄호값의 합과 같다. 따라서 변수 x를 두어 현재 열린 괄호로 인한 괄호값을 소괄호면 두 배, 대괄호면 세 배를 해주며 키우다가 닫힌 괄호를 만났을 때 한번에 계산을 해주면 된다. 이때 해당 덩어리의 값을 닫힌 괄호를 만나면 업데이트하기에 직전 괄호가 열린 괄호일 때 한번만 갱신해주며 더해나가줬다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        Deque<Character> stack = new ArrayDeque<>();
        int sum = 0;
        int x = 1;

        String s = br.readLine();
        char prv = '\u0000';

        for (char c : s.toCharArray()) {
            if (c == '(') {
                x *= 2;
                stack.push(c);
            } else if (c == '[') {
                x *= 3;
                stack.push(c);
            } else if (c == ')') {
                if (stack.isEmpty() || stack.peek() != '(') {
                    System.out.println(0);
                    return;
                }

                if (prv == '(') sum += x;
                x /= 2;
                stack.pop();
            } else {
                if (stack.isEmpty() || stack.peek() != '[') {
                    System.out.println(0);
                    return;
                }

                if (prv == '[') sum += x;
                x /= 3;
                stack.pop();
            }

            prv = c;
        }

        if (stack.isEmpty()) {
            System.out.println(sum);
        } else {
            System.out.println(0);
        }
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    stack<char> st;
    int sum = 0;
    int x = 1;

    string s;
    cin >> s;
    char prv = '\0';

    for (char c : s) {
        if (c == '(') {
            x *= 2;
            st.push(c);
        } else if (c == '[') {
            x *= 3;
            st.push(c);
        } else if (c == ')') {
            if (st.empty() || st.top() != '(') {
                cout << 0;
                return 0;
            }

            if (prv == '(') sum += x;
            x /= 2;
            st.pop();
        } else {
            if (st.empty() || st.top() != '[') {
                cout << 0;
                return 0;
            }

            if (prv == '[') sum += x;
            x /= 3;
            st.pop();
        }

        prv = c;
    }

    if (st.empty()) {
        cout << sum;
    } else {
        cout << 0;
    }
}

---

3. 디버깅

없음.

---

4. 참고

없음.

---