(백준/C++) 4949번_균형잡힌 세상

4949번: 균형잡힌 세상 (acmicpc.net) 문제는 Stack을 활용한 짝 맞추기 문제입니다.

괄호의 짝이 잘 맞는지(여는 괄호와 닫는 괄호의 짝이 맞는지) 확인하고, 짝이 맞거나 없다면(틀린 짝이 없다면) ‘yes’를, 짝이 틀리면 ‘no’를 출력하는 문제입니다.

이전에, 9012번: 괄호 (acmicpc.net) 문제를 풀어보셨다면 쉽게 풀 수 있는 문제입니다.

이전 괄호 포스트는 flag를 사용했다면, 이번 포스트에서는 센티널 값을 사용하겠습니다.

주의 사항

문제 풀이 중 간과하기 쉬운 두 가지 포인트가 있습니다.

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

풀이 과정

이 문제를 풀 때, flag나 잘못된 값을 이용하는 접근 방식이 있습니다. 이 문제는 잘못된 값(센티널 값)을 넣어서 풀었고, flag를 활용한 방법은 이전 포스팅을 참조해 주세요.

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

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

#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    while(true)
    {
        stack<char> pare;
        string str;
        getline(cin.ignore(), str, '.');
        if (str.empty()) break;
        for (char& c : str)
        {
            //여는 괄호 처리
            if(c == '(' || c == '[')
            {
                pare.push(c);
            }
            //닫는 괄호 처리
            else if(c == ')' || c == ']')
            {
                if (pare.empty() ||
                    (c == ')' && pare.top() != '(') ||
                    (c == ']' && pare.top() != '[')
                    )
                {
                    pare.push('.');
                    break;
                }
 
                pare.pop();
            }
        }
        //결과 출력
        cout << (pare.empty() ? "yes" : "no") << '\n';
    }
}

이 코드는 스택이 비어있거나 괄호의 짝이 일치하지 않을 때, 특별한 값을 추가하여 결과를 판단하도록 했습니다.