< BOJ > 9012 - 괄호

문제

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

9012번: 괄호

9012번 제출 맞은 사람 숏코딩 풀이 풀이 작성 풀이 요청 재채점/수정 채점 현황 강의 괄호 풀이 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 128 MB 17686 6815 5228 38.783% 문제 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 &ld

www.acmicpc.net

괄호 문자열(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”를 한 줄에 하나씩 차례대로 출력해야 한다.

 

테스트케이스

6 (())()) (((()())() (()())((())) ((()()(()))(((())))() ()()()()(()()())() (()((())()(

 

 

해결방법

괄호의 개수를 비교하여야 하므로 stack이나 vector를 이용하여 해결할 수 있다고 생각했다.

실제로 stack을 이용하여 스택에 넣은 후 비어있는 등 상태를 이용하여 올바른 VPS인지 판단할 수 있었다.

 

코드

#include<cstdio>
#include<iostream>
#include<stack>
#include<string>
#include<cstring>

using namespace std;

int main() {

	int n;
	char c[100];
	scanf("%d", &n);

	for (int j = 0; j<n + 1; j++) {
		stack<int> s;
		fgets(c, 100, stdin);
		int len;
		len = strlen(c);
		c[len - 1] = '\0';
		int size = 0;
		while (c[size++]);
		for (int i = 0; i<size - 1; i++) {
			if (c[i] == '(') s.push(1);
			else if (c[i] == ')') {
				if (s.empty()) {
					printf("NO\n");
					break;
				}
				else s.pop();
			}
			if (i == size - 2) {
				if (s.empty()) printf("YES\n");
				else printf("NO\n");
			}
		}

	}
	return 0;
}

 

배운점, 주의할 점

1. #include<cstring>

이부분은 생각을 잘 하지 못했는데 VS에서는 알아서 컴파일을 해주는 건지 에러가 나지 않았는데 백준 사이트에서는 gcc를 사용하기에 cstring을 헤더로 컴파일 하지 않으면 gets나 fgets를 사용할 수 없어 컴파일 에러가 나게 된다.

 

2. fgets()

원래 gets를 주로 사용했는데 gets에는 함수의 크기 제한이 없이 문자열을 받기 때문에 추천하지 않는다.

즉 char str[10]; 짜리에 11글자를 입력하게 되면 오류가 발생한다.

그래서 사용을 추천한 것이 fgets인데 gets보다는 복잡하다.

fgets( 문자열, 크기, 입력 형태 ) 의 순서로 입력하게 된다.

그리고 중요한 특징으로는 fgets는 \n 즉 줄바꿈 문자를 문자열에 함께 받게 된다.

따라서 위의 코드에서처럼 마지막 부분을 \0 등으로 공백처리를 해주어야 문자열만 저장할 수 있다.

3. stack.empty() 등

함수를 사용시에 뒤에 ()를 붙여주는 것은 너무나도 간단한 일이다.

하지만 오랜만에 C를 사용하니 기본적인것도 헷갈렸다.