백준 9012 괄호 c++ [컴공과고씨]

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

9012번: 괄호

이 문제를 보고 처음에는 당연히 queue를 떠올리기 어려울 수 있지만 한 번 직접 괄호 지우다 보면 queue가 떠올라야한다. 

이런식으로 앞에 나온 ( 가 있다면 ) 나왔을 때 (을 지워주는 형식으로 할 것이다. 그런데 만약 남아있는 ( 있거나 ( 가 나오지 않았는데 ) 나온다면 그것도 잘못된 괄호이다. 그래서 큐를 이용하는 것이다.

먼저 ( 일 경우 큐에 push 해주고 만약 ) 나왔다면 큐에서 pop해주면 된다.

이때 큐가 비어있는데 pop을 하려고 하면 no를 출력 만약 마지막 까지 연산이 끝났는데 큐가 비어있지 않으면 ( 남아있다는 것이니 이것도 no를 출력해주면 된다.

 

단계별 풀이

1. 입력 된 값을 하나씩 보면서 ( 가 나오면 큐에 push 해준다.

2. 만약 ) 나왔다면 먼저 큐가 비어있는지 확인해서 비어있다면 no를 출력해준다.

3. 만약 비어있지 않다면 큐를 pop해준다.

4. 연산이 끝난 후 큐가 비어있다면 yes를 비어있지 않다면 no를 출력해준다.

 

전체코드

 

#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main(){
    int n;
    string s;
    cin >> n;
    
    for (int i = 0; i < n; i++){
        queue<char> q;
        cin >> s;
        bool flag = true;
        for (int i = 0; i < s.length();i++){         
            if (s[i] == '('){
                q.push(s[i]);
            }
            else{
                if (q.empty()){ // ( 가 없는데 ) 나옴
                    cout << "NO" << '\n';
                    flag = false;
                    break;
                }
                q.pop();
            }
        }
        if(flag){
            if(q.empty()){
                cout << "YES"<< '\n';
            }else{ // ( 가 남아있음
                cout << "NO"<< '\n';
            }
        }
    }
 
    return 0;
} //16min

체감 난이도	걸린시간	참고	사용 문법
하	16min	x	queue