[PS] 백준 9012 괄호

이번에는 백준 9012번 괄호 문제를 풀어보았습니다.

이 문제는 입력으로 주어진 괄호 문자열이 올바른 괄호 문자열인지 아닌지를 판단하는 문제입니다.

핵심은 '('와 ')'의 짝이 올바르게 맞는지 확인하는 것이었고,

그래서 자연스럽게 stack 자료구조를 사용하게 되었습니다.

---

문제 설명

괄호 문자열은 '(', ')'만으로 이루어진 문자열입니다.

이 중에서 괄호의 짝이 올바르게 맞는 문자열을 VPS(Valid Parenthesis String) 라고 합니다.

예를 들어

• "()"
• "(())()"
• "((()))"

는 VPS이고,

• "(()("
• "(())()))"
• "(()"

는 VPS가 아닙니다.

입력으로 여러 개의 괄호 문자열이 주어질 때,

각 문자열이 VPS이면 "YES", 아니면 "NO"를 출력하면 됩니다.

---

풀이 아이디어

이 문제는 괄호의 짝을 찾는 문제이기 때문에 stack을 사용했습니다.

기본 아이디어는 다음과 같습니다.

• '('가 들어오면 push
• ')'가 들어오면 pop

이 과정을 문자열 끝까지 반복하면 됩니다.

다만 중간에

• 스택이 비어 있는데 ')'가 들어오는 경우

는 바로 잘못된 문자열입니다.

그리고 문자열을 전부 확인한 뒤에도 스택이 비어 있지 않다면,

짝이 맞지 않은 '('가 남아 있다는 뜻이므로 역시 올바른 문자열이 아닙니다.

---

V1 코드

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

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;
    vector<int> ret;
    for (int i = 0; i < N; i++) {
        string s;
        cin >> s;
        stack<char> stk;
        bool flag = true;
        for (int j=0; j<s.length(); j++) {
            if (stk.empty()) {
                if (s[j] != '(') {
                    flag = false;
                    break;
                }
                stk.push(s[j]);
            } else {
                if (s[j] == ')') {
                    stk.pop();
                } else {
                    stk.push(s[j]);
                }
            }
        }

        if (!stk.empty())
            flag = false;

        if (flag)
            ret.push_back(1);
        else
            ret.push_back(0);
    }

    for (int i = 0; i < ret.size(); i++) {
        if (ret[i])
            cout << "YES\n";
        else
            cout << "NO\n";
    }

    return 0;
}

---

풀이 흐름

1. 테스트 케이스 개수 N을 입력받는다.
2. 각 문자열마다 스택을 하나 새로 만든다.
3. 문자열을 앞에서부터 한 글자씩 확인한다.
4. '('가 들어오면 push 한다.
5. ')'가 들어왔을 때 스택이 비어 있으면 잘못된 문자열로 처리한다.
6. 문자열을 모두 확인한 뒤에도 스택이 비어 있지 않으면 잘못된 문자열로 처리한다.
7. 각 결과를 YES 또는 NO로 출력한다.

---

구현 포인트

1. 괄호 짝 문제이기 때문에 stack 선택

이 문제는 여는 괄호와 닫는 괄호의 짝을 맞추는 문제입니다.

그래서 가장 최근에 들어온 '('와 현재 ')'를 대응시키는 방식이 자연스럽고,

이런 구조에는 stack이 잘 맞습니다.

즉,

• '(' → push
• ')' → pop

이라는 흐름으로 생각할 수 있습니다.

---

2. 스택이 비어 있을 때 ')'가 들어오면 바로 실패

코드에서는 스택이 비어 있는 상태를 먼저 확인했습니다.

if (stk.empty()) {
    if (s[j] != '(') {
        flag = false;
        break;
    }
    stk.push(s[j]);
}

이 부분의 의미는,

스택이 비어 있는데 현재 문자가 ')'라면 짝을 맞출 '('가 없다는 뜻이므로

그 문자열은 VPS가 아니라는 것입니다.

그래서 바로 flag = false로 처리하고 반복을 종료했습니다.

---

3. 스택이 비어 있지 않을 때는 ')'면 pop, '('면 push

스택 안에 '('가 들어 있는 상태라면

• 현재 문자가 ')'면 짝이 맞는 것이므로 pop
• 현재 문자가 '('면 새로운 여는 괄호이므로 push

하도록 처리했습니다.

if (s[j] == ')') {
    stk.pop();
} else {
    stk.push(s[j]);
}

즉, 문자열을 왼쪽부터 보면서 계속 짝을 맞춰나가는 방식입니다.

---

4. 끝까지 갔는데 스택이 남아 있으면 실패

문자열을 전부 확인한 뒤에도 스택이 비어 있지 않다면,

아직 짝이 맞지 않은 '('가 남아 있다는 뜻입니다.

if (!stk.empty())
    flag = false;

예를 들어 "(()" 같은 경우는 중간에 잘못된 순간은 없더라도,

마지막에 '(' 하나가 남기 때문에 VPS가 아닙니다.

---

5. 결과는 바로 출력하지 않고 벡터에 저장

이 코드에서는 각 테스트 케이스의 결과를 바로 출력하지 않고 ret 벡터에 저장한 뒤,

마지막에 한 번에 출력하도록 했습니다.

if (flag)
    ret.push_back(1);
else
    ret.push_back(0);

그리고 마지막에

if (ret[i])
    cout << "YES\n";
else
    cout << "NO\n";

형태로 출력했습니다.

---