[C++]4949번: 균형잡힌 세상

요약

• stack을 이용한 조건 체크

풀이과정

괄호 체크 문제는 전형적인 stack 문제이다.

string에서 모든 char에 대해 아래의 조건을 검사한다.

 

1. (, [ 일 때

- stack에 해당 char push

2. )일 때

- stack이 비어있지 않고, top 값이 ( 라면 PUSH

- else : no 출력하고 break

3. ]일 때

- stack이 비어있지 않고, top 값이 [ 라면 PUSH

- else : no 출력하고 break

모든 검사가 끝난 후

stack이 비어있지 않다면

- no 출력

 

여기서 주의할 점은 stack.top() 을 호출할 때 stack이 비어있다면 segmentation fault가 발생하니,

top은 비어있지 않은지 앞쪽에 AND 조건으로 검사해준다.

코드

#define LOCAL




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

const string Y = "yes";
const string N = "no";

int main() {
    #ifdef LOCAL
    freopen("input.txt","r",stdin);
    #endif
    cin.tie(0) -> sync_with_stdio(0);

    while (true)
    {
        string str, answer(Y);
        getline(cin, str);
        if(str == ".")  //마지막 온점 하나 입력일 경우 종료 처리
            break;
        
        stack<char> s;
        for(char c : str) { //문자열의 모든 char에 대해 검사
            if(c == '(' || c == '[') {
                s.push(c);
            }
            else if(c == ')') {
                //check last pushed value is '('
                if(!s.empty() && s.top() == '(') {    //정상, pop
                    s.pop();
                }
                else {    //비정상, break하고 no 저장
                    answer = N;
                    break;
                }
            }
            else if(c == ']') {
                //check last pushed value is '['
                if(!s.empty()&& s.top() == '[') {    //정상, pop
                    s.pop();
                } else {    //비정상, break하고 no 저장
                    answer = N;
                    break;
                }
            }
        }
        //stack이 비어있는지 검사
        if(!s.empty())
            answer = N;

        cout << answer << endl;
    }
    

}

다른 사람의 풀이

다들 stack을 활용하였다. 

정규 표현식으로 sub을 활용해 괄호 관련 문자를 제외하고 지우는 방법도 있다. 

그러나 괄호 검사를 해야하는 점은 여전하므로 따로 구현해보지 않았다.