[백준/C++] 9012: 괄호

 문제

 

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다. 

 

 입력

 

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다. 

 

 출력

 

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다. 

 

 소스 코드

#include <iostream>

using namespace std;

int main()
{
    int T;
    cin >> T;

    string temp, result[T];
    int a, b, cnt;
    for ( int i = 0; i < T; i++ )
    {
        a = 0, b = 0, cnt = 0;

        cin >> temp;
        for ( int j = 0; j < temp.size(); j++ )
        {
            if ( temp[j] == '(' ) a++;
            else b++;
            if ( b > a )
            {
                cnt++;
                break;
            }
        }

        if ( a == b && cnt == 0) result[i] = "YES";
        else result[i] = "NO";
    }

    for ( int i = 0; i < T; i++ ) cout << result[i] << "\n";
}

 문제 풀이

1. 테스트 데이터의 수 T를 입력 받는다.

[ temp (괄호를 입력받을 역할), result[T] (출력 데이터인 "YES" or "NO"를 저장할 배열), a ('('의 개수), b (')'의 개수), cnt (result에 들어갈 출력 데이터를 결정하는 숫자 ]

2. '('를 만나면 a를 1 증가, '('를 만나면 b를 1 증가시킨다. 이때, b가 a보다 크다면 열린 괄호가 없음에도 닫힌 괄호가 나온 것이므로 NO를 저장해야한다. 이미 NO를 봤기 때문에 cnt가 증가하고, 내부에 있는 for반복문을 탈출한다.

3. 모든 T 경우를 다 확인하고 result에 있는 값들을 차례대로 출력한다.