[백준/BOJ] 9012번 괄호 (C/C++)

백준 온라인 저지(BOJ) 9012번 괄호

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

9012번: 괄호

* 사용언어 : C언어, C++

 

1. 문제

T개의 테스트 케이스 괄호 문자열에 대해서

모양이 바르게 구성된 VPS(Valid Parenthesis String)인 경우 YES, 아닌 경우 NO를 출력

 

2. 풀이

Stack 자료구조를 활용하여 풀 수 있는 문제입니다.

입력 문자열을 한 글자 씩 탐색하면서 '('가 나오면 Stack에 넣고, ')'가 나오면 Stack에서 빼는 방식입니다.

 

만약 Stack에 값이 없는데 pop을 시도하거나(size가 음수)

마지막 문자열까지 처리했는데 Stack에 값이 남아있다면(size가 양수),

VPS가 아닌 것으로 보고 NO를 출력하고 아니면 YES를 출력했습니다.

 

 

설계를 마치고 보니 Stack에 들어가는 값이 '(' 하나 뿐이라는 것을 알 수 있었습니다.

 

그래서 구현할 때는 Stack에 굳이 char문자를 직접 넣거나 빼지 않고,

Stack의 크기를 의미하는 size라는 int 변수 하나만을 증가, 감소시키면서 같은 결과를 냈습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
9012_괄호
1112KB	0ms
*/
#include <cstdio>

const int LM = 51;
char input[LM], *c;
// char st[LM];
int size, t, valid;

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &t);
	while (t--) {
		size = 0;
		valid = 1;

		scanf("%s", input);
		c = (char*)input;
		while (*c) {
			if (*c == '(') ++size;
			else --size;

			if (size < 0) {
				valid = 0;
				break;
			}
			++c;
		}

		if (valid && !size) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}