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

문제 링크

---

1. 아이디어

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

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

결국 괄호열의 값은 안쪽에 아무것도 없는 쌍마다 그 쌍과 그 쌍을 감싼 모든 괄호의 값(소괄호는 2, 대괄호는 3)을 곱해 전부 더한 것과 같다. 올바르지 않은 괄호열은 닫는 괄호를 만났을 때 스택이 비어 있거나 맨 위가 짝이 맞지 않는 경우, 또는 끝까지 읽고도 스택에 괄호가 남은 경우이므로 이때는 0을 출력했다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N)$	$O(N)$

($N$ = s의 길이)

---

3. 코드

풀이 [Java][C++]

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);
        }
    }
}

#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;
    }
}

---