백준9012 괄호

작성일 | In

문제 링크

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

문제 출처

  • 2012 ACM-ICPC 대전 인터넷 예선 G번

사용 알고리즘

  • 스택

시간복잡도

  • O(Tn)

풀이

괄호 짝 관련 문제는 경우의 수를 구하지 않는 이상 스택 구조를 사용하는 경우가 많습니다.
이 문제도 스택을 이용해 풀어봅시다.

백준 9012같은 문제는 여는 괄호는 push하고, 닫는 괄호가 나오면 pop을 해가며 푸는 것이 일반적입니다.
이 문제의 해결법은 간단합니다.
위에서 말한 대로
“여는 괄호는 push, 닫는 괄호는 pop을 해서 마지막에 size가 0이 되면 true, 0이 아니면 false다.”
라고 생각하기 쉽지만, 사실은 한 가지 조건이 더 추가가 됩니다.
underflow가 일어나면, 즉 열린 괄호는 없는데 닫으려고 하는 경우에도 false가 됩니다.

여는 괄호가 나오면 push하고
닫는 괄호가 나오면 pop을 하는데 중간에 underflow가 발생하면 false가 되고
모든 괄호를 다 처리 했을 때 스택의 size가 0이면 true, 0이 아니면 false입니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n; scanf("%d", &n);
    while(n--){
        char str[100]; scanf("%s", str);
        stack<int> s;
        bool flag = false;
        int len = strlen(str);
        for(int i=0; i<len; i++){
            if(str[i] == '(') s.push(1);
            else{
                if(s.empty()){
                    printf("NO\n");
                    flag = true;
                    break;
                }else s.pop();
            }
        }
        if(s.empty() && !flag) printf("YES\n");
        else if(!flag) printf("NO\n");
    }
}