[C++] BOJ 9012번: 괄호

학교에서 진행하는 수업에서 공유받은 알고리즘 문제를 풀어보았다. 문제의 난이도는 실버 4로, 스택 자료구조를 활용하여 푸는 문제이다. 수업 시간에 발표를 들으며 알게된 것이지만, 사실 스택 자료구조를 사용하지 않고도 문제를 풀 수 있다. 하지만 여기서는 스택 자료구조를 활용하여 푼 방식을 작성할 것이다.

문제 링크

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

문제 분석

괄호 쌍이 적절하게 맞는지 확인하는 문제이다. 괄호 쌍이 맞는다는 건 단순히 '('와 ')'의 갯수가 같으면 되는 것이 아니라, '('와 ')'의 순서도 맞아야 하기 때문에 갯수를 세는 방식으로 문제를 풀면 답이 틀리게 된다.

문제 풀이

스택 자료구조를 활용하여 문제를 해결하였다.

입력값을 순회하며 char형 ch에 대해 다음의 과정을 수행한다.

1. ch가 '('인 경우 스택에 push한다.
2. ch가 ')'인 경우 스택의 top이 '('인 경우엔 pop한다.
3. ch가 ')'인 경우 스택이 비어있다면 스택에 ')'를 push한다. (이 때, 스택에 push하는 값은 '('만 아니면 아무 값이나 상관 없다)

위와 같이 작업을 진행하였을 때 스택이 비어있다면 짝이 맞다는 뜻이고, 스택이 비어있지 않다면 짝이 맞지 않다는 뜻이다.

 

따라서 순회가 끝난 후 스택이 비어있는지 확인하고 비어있으면 "YES"를, 비어있지 않으면 "NO"를 출력한다.

전체 코드

#include <iostream>
#include <stack>

using namespace std;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;

    cin >> N;

    while (N--)
    {
        stack<char> s;
        string input;
        cin >> input;

        for (char ch : input)
        {
            if (ch == '(')
            {
                s.push(ch);
            }
            else if (ch == ')')
            {
                if (!s.empty() && s.top() == '(')
                    s.pop();
                else
                    s.push(ch);
            }
        }

        if (s.empty())
            cout << "YES" << '\n';
        else
            cout << "NO" << '\n';
    }

    return 0;
}