괄호

9012번: 괄호 (acmicpc.net)

9012번: 괄호

예제 입력 1

6

(())())

(((()())()

(()())((()))

((()()(()))(((())))()

()()()()(()()())()

(()((())()(

예제 출력 1

NO

NO

YES

NO

YES

NO

예제 입력 2

3

((

))

())(()

예제 출력 2

NO

NO

NO

 

 

- 스택을 사용하여 풀 수도 있지만, 간단한 방법이 있다.

- cnt 변수를 두고 0으로 시작하여 '(' 이면 증가시키고 ')'이면 감소시킨다.  최종적으로 cnt == 0이면 올바른 괄호이다.

- 단, cnt == 0일 경우라도 올바른 괄호가 아닌 경우가 있다.

  ex. )(()

  따라서, 조건이 하나 더 필요한데, cnt가 0보다 작으면 현재 열린괄호 수보다 닫힌 괄호 수가 더 많다는 의미이므로, 잘못된 괄호로 판정하면 된다.

#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h>

const int MAX_SIZE = 55;

int main(void)
{
	int TC = 0;
	scanf("%d", &TC);
	
	while (TC-- > 0)
	{
		char input[MAX_SIZE + 1];

		int cnt = 0;

		scanf("\n%s", input);

		for (int i = 0; input[i]; i++)
		{
			if (input[i] == '(') cnt++;
			else if (input[i] == ')') cnt--;

			if (cnt < 0) break;
		}

		if (cnt == 0)
			printf("YES\n");
		else
			printf("NO\n");
	}

	return 0;
}