(백준/C++) 9012번_괄호

9012번: 괄호 (acmicpc.net) 문제는 Stack에 관한 문제로, 짝이 맞는지 안맞는지 테스트하는 동작을 만드는 짝 맞추기 문제입니다.

스택의 순서 보장과 역순서 보장의 특성을 이용해 마지막에 넣은 값과 짝이 맞는지 확인하기만 하면 되는 문제입니다.

주의 사항

이 문제를 풀어가는데 있어서 쉽게 넘어갈 수 있는 주의해야 할 점은 다음 두가지 입니다.

1. 닫는 괄호 입력시 스택을 확인하되, 비어있으면 버어있던 경우도 확인 되어야 합니다.
2. 닫는 괄호를 처리하려고 스택의 top()을 사용하는 순간, 스택이 비어있으면 안됩니다.

풀이 과정

저는 이 문제를 풀 때, flag나 잘못된 값을 넣어서 처리하는 방법을 떠올렸습니다. 이 문제는 flag를 넣어서 풀었고, 잘못된 값을 넣어서 푸는 방법은 균형잡힌 세상 포스트를 참고해주세요.

여기에서 잘못된 값이란, 특정 조건을 표시하기 위해 넣은 값입니다. 이를 센티널 값(sentinel value) 또는 보초 값이라고도 부른다고 하는데, 이 경우에도 해당되는 용어인지는 잘 모르겠습니다.

컴퓨터 프로그래밍에서 센티넬 값(플래그 값, 트립 값, 불량 값, 신호 값 또는 더미 데이터라고도 함)은 일반적으로 루프 또는 재귀 알고리즘에서 종료 조건으로 존재를 사용하는 알고리즘의 맥락에서 특별한 값입니다.

C++ 표준 라이브러리인 <string>과 <stack>을 그대로 사용했습니다.

#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int N;
    cin >> N;
    while (N--)
    {
        bool flag = true;
        string pare;
        stack<char> s;
        cin >> pare;
        for (const char& c : pare)
        {
            if (c == '(')
            {
                s.push(c);
            }
            else if (c == ')')
            {
                if (!s.empty() && s.top() == '(')
                {
                    s.pop();
                }
                else
                {
                    flag = false;
                    break;
                }
            }
        }
 
        if (s.empty() && flag)
            cout << "YES" << '\n';
        else
            cout << "NO" << '\n';
    }
}

이 문제는 flag를 만들고, 잘못된 값이 들어오면 flag를 flase로 만들어서 반복문을 종료시킵니다.