[알고리즘/문제풀이/BOJ 9012번] 괄호

괄호 문제는 스택의 특성을 활용하여 해결할 수 있는 문제입니다. 괄호의 문장이 완결되기 위해서는 여는 괄호와 닫는 괄호의 짝이 맞아야 합니다. 여는 괄호일 때 스택에 push하고 닫는 괄호일 때 스택에 pop을 함으로써 괄호의 짝이 맞는지 확인할 수 있습니다. 편의상 스택까지 구현하지 않고  스택의 가장 윗 원소를 표시하는 top만 선언하여 여는 괄호일 때 +1 닫는 괄호일 때 -1이 되도록 하였습니다. 이 때 주의할 점은 괄호 문장을 검색하는 중 top이 -1이 되면 그것은 닫는 괄호의 짝이 맞지 않는다는 뜻이며 즉시 탈출해서 NO를 출력해야 합니다. 그렇지 않으면 괄호의 짝이 맞지 않아도 top이 0이 되는 경우에 잘못된 값을 출력하게 됩니다. 실제로 pop함수를 구현하지 않아서 생기는 문제이므로 직접 스택을 구현한다면 고려할 필요가 없을 것 같습니다.

작성한 코드는 다음과 같습니다.

---

#include<stdio.h>
//http://ark-hive.tistory.com/
int T;
char parenthesis;
int top;

int main(void) {
	scanf("%d%*c", &T);

	for (int i = 0; i < T; i++, top = 0) {
		while ((parenthesis = getchar()) != '\n') {
			if (parenthesis == EOF) break;
			if (parenthesis == '(') top++;
			else top--;

			if (top < 0) {
				while ((parenthesis = getchar()) != '\n') {
					if (parenthesis == EOF) break;
				};
				break;
			}
		}
		if (top == 0) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

문제의 지문은 다음의 링크에서 확인할 수 있습니다.

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