백준 9012 괄호 - C++ 풀이 공유

문제링크

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

시사점

해당 문제에서 조심할 점이 있었다.

1. ))(( 의 경우 괄호의 갯수는 같으나 매칭이 되지 않습니다.

이점을 고려하지 않으면, 시간이 복잡도가 올라갈 경우가 많습니다.

/******
 * Author      :    Jiung
 * Filename    :    9012-괄호.cpp
 * Version     :    Apple clang version 12.0.0 (clang-1200.0.32.27)
 * Date        :    2021-02-24
 * Copyright   :    Free
 */

#include <iostream>

using namespace std;
  /*
   * 괄호가 정확히 매칭되는지 확인하는 함수
   */
void checkString(string check) {

    int a=0;

    /*
     * string 의 길이를 하나하나 검사합니다.
     * 하지만, 중간에 )이 하나 더 온다면,
     * 괄호를 매칭할 수 없게 됩니다.
     */
    for(int j=0; j<check.length(); j++) {
            if (check[j] == '(') {
                a += 1;
            } else {
                a -= 1;
            }
            if (a < 0) {
                cout << "NO" << endl;
                return;
            }
        }

    /*
     * 만약 a값이 더 크다면, ( 가 더 많다는 뜻이다.
     * 따라서, 괄호가 매칭이 되지 않습니다.
     */
    if ( a != 0 ) {
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
    }
    // 함수 종료
    return ;
}
int main() {
    int n;
    cin >> n;
    string check;
    /*
     * 반복문을 통해서 예제를 입력받습니다.
     */
    for(int i=0; i<n; i++) {
        cin >> check;
       checkString(check);
    }
}

감사합니다.