[Baekjoon(백준)][9012번] 괄호(C++)

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "괄호" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제에서는 주어진 괄호 문자열이 올바른 괄호 문자열(Valid PS, VPS)인지 판단해야 합니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크:

https://www.acmicpc.net/problem/9012

9012번: 괄호

문제 개요

"괄호" 문제에서는 주어진 괄호 문자열이 올바른 괄호 문자열(Valid PS, VPS)인지 판단해야 합니다. 올바른 괄호 문자열이란, 괄호의 쌍이 정확하게 맞아 떨어지는 경우를 말합니다.

해결 방법

문제 해결을 위해서는 스택을 사용합니다. 여는 괄호 '('를 만나면 스택에 넣고, 닫는 괄호 ')'를 만나면 스택에서 꺼냅니다. 만약 스택이 비어있는데 닫는 괄호를 만나면 올바르지 않은 괄호 문자열입니다.

코드 구현

#include <iostream>
#include <stack>

using namespace std;

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

    int n = 0;
    cin >> n;
    while (n--) {
        string str = "";
        cin >> str;
        if (str[0] == ')') {
            cout << "NO" << "\n";
            continue;
        }
        stack<char> s;
        bool isPrinted = false;
        for (int i = 0; i < str.size(); i++) {
            // 여는 괄호는 스택에 넣는다
            if (str[i] == '(') {
                s.push(str[i]);
            } else {
                // 닫는 괄호인 경우 스택에서 꺼낸다
                if (s.size()) s.pop();
                else {
                    cout << "NO" << "\n";
                    isPrinted = true;
                    break;
                }
            }
        }
        if (isPrinted) continue;
        // 스택에 남아있는 괄호가 없다면 올바른 괄호 문자열
        if (s.size() > 0) cout << "NO" << "\n";
        else cout << "YES" << "\n";
    }
}

코드 설명

스택을 사용하여 여는 괄호와 닫는 괄호를 관리합니다. 여는 괄호가 나오면 스택에 넣고, 닫는 괄호가 나오면 스택에서 꺼냅니다. 만약 닫는 괄호를 만났을 때 스택이 비어있다면, 이는 올바르지 않은 괄호 문자열을 의미합니다. 또한, 모든 문자를 확인한 후 스택에 여는 괄호가 남아있으면 이 또한 올바르지 않은 괄호 문자열입니다.

결론

"괄호" 문제는 스택을 이용하여 간단하게 해결할 수 있습니다. 스택을 사용해 괄호의 쌍을 관리함으로써 올바른 괄호 문자열을 판별할 수 있습니다.