백준 알고리즘 - 9012번 : 괄호

백준 알고리즘 - 9012번 : 괄호 문제입니다.

(참고 - https://www.acmicpc.net/problem/9012 )

코드 ) 

#include <stdio.h> 

#define MAXSIZE 50

int main() {

    int i, j, cnt, num;

    char arr[MAXSIZE];

    scanf("%d", &num);

    for ( j = 0; j < num; j++) {

        cnt = 0;

        scanf("%s", arr);

        for ( i = 0; i < MAXSIZE; i++) {

            if ( arr[i] == '\0')

                break;

            if ( arr[i] == '(')

                cnt++;

            else if ( arr[i] == ')' && cnt > 0)

                cnt--;

            else if ( arr[i] == ')' && cnt <= 0) {

                cnt--;

                break;

            }

        }

        if ( cnt == 0 )

            printf("YES\n");

        else

            printf("NO\n");

    }

}

- 어려워보일수도 있지만, 생각해보면 간단한 문제입니다. 먼저 문자열을 char형 배열에 입력받습니다.

char형은 각 주소번지마다 1Byte만큼 저장할 수 있으므로 '(' 혹은 ')' 문자 하나하나가 각 인덱스에 저장될 것입니다.

char형 배열 arr에 저장된 값을 인덱스 0부터 차례대로 검사하며 '(' 문자이면 카운트를 더해주고, ')' 문자이면 카운트를 감소시켜줍니다.

'(' 문자라면 단순히 카운트를 더해주면 되지만, ')'문자라면 검사해야 할 조건이 늘어납니다. 

VPS의 조건을 성립시키기 위해 만약 카운트가 0, 즉 ')' 문자와 상쇄되어야 할 '(' 문자가 없는 상태에서 ')' 문자가 한번 더 오게 되면 그 이후에는 '(' 문자나 ')' 문자에 관계없이 VPS 의 조건을 성립하지 않으므로 검사할 필요가 없습니다.

따라서 바로 break를 통해 검사하는 for문을 빠져나오게 되고, cnt는 -1의 값을 갖게 될 것입니다.  즉 cnt==0이라는 조건이 되지않아 NO 라는 문자열을 출력할 것입니다.

만약 VPS의 조건을 성립하여 ( 문자와 )문자가 제대로 상쇄되었다면 cnt==0 으로 결론이 나와서 YES라는 문자열을 출력해 줄 것입니다.