BOJ 09012(괄호) 문제 풀이

목차

• 참조
• 개요
  • 시간복잡도: $ O(TC \cdot L) $
  • 공간복잡도: $ O(L) $
• 문제 풀이
• 구현

참조

개요

시간복잡도: $ O(TC \cdot L) $

공간복잡도: $ O(L) $

• TC는 테스트 케이스의 수, L은 문자열의 길이이다.

문제 풀이

괄호 짝 맞추기는 스택 문제의 단골손님이다.
이 문제의 핵심 아이디어는 다음과 같다.

• 문자열을 하나씩 읽는다.
  • 여는 괄호 ( 가 나오면 스택에 집어넣는다.
  • 닫는 괄호 ) 가 나오면 괄호 하나를 빼낸다.
    • 이때 스택이 비어 있으면 잘못된 것이다. NO를 출력한다.
• 문자열을 다 읽고 나서 스택이 비어 있어야만 제대로 된 Parenthesis String이다. YES를 출력한다.
  • 스택에 뭔가 들어 있으면 NO를 출력한다. 이 부분이 실수가 가장 많이 나오는 부분이다.
• 각 테스트 케이스마다 스택을 clear시켜줘야 한다. 안 그러면 wrong answer를 받을 것이다.

구현

이 문제에는 적용 가능한 트릭이 몇 가지 있다. 코딩을 간단하게 만들 수 있다.

• 이 문제는 스택에 집어넣는 것이 오직 여는 괄호 ( 하나 뿐이다. 그럼 굳이 스택을 쓸 것도 없이, 쌓인 여는 괄호의 수를 세어 줄 변수 n 하나만 있으면 된다.
• 각 문자마다 검사할 때, 닫는 괄호 ) 가 나오면 일단 n을 감소시킨다. 그리고 n이 0보다 작아지면, 바로 중단한다.
  • 그러면 마지막에서 n이 0인지만 보면 YES / NO 를 판별할 수 있다.

#include <string>
#include <iostream>

using namespace std;

int main_09012() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);    cin.tie(NULL);

    int TC;

    cin >> TC;
    while (TC--) {
        int n = 0;
        string str;
        cin >> str;
        for (auto s : str) {
            if (s == '(')
                ++n;
            else 
                --n;
            if (n < 0)break;
        }
        cout << (n ? "NO" : "YES") << '\n';
    }
    return 0;
}

주의: 이 코드를 그대로 복붙하여 채점 사이트에 제출하면 틀린다. 그대로 제출하지 말라는 뜻이다. 무언가를 바꿔 주어야 한다.