[Baekjoon/C++] 9012번 - 괄호

Baekjoon Online Judge

문제로 이동

 

문제

괄호 문자열(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 (())()) (((()())() (()())((())) ((()()(()))(((())))() ()()()()(()()())() (()((())()(	NO NO YES NO YES NO
3 (( )) ())(()	NO NO NO

---

풀이

#include <iostream>
using namespace std;

struct stack {
	char data[51];
	int top;
};

// 초기화
void init(stack* s) {
	s->top = -1;
}

// 삽입 함수
void push(stack* s, int n) {
	s->data[++(s->top)] = n;
}

// 삭제 함수
char pop(stack* s) {
	return s->data[(s->top)--];
}

// 스택이 비어있는지 확인
bool isEmpty(stack* s) {
	return (s->top == -1);
}

// 맨 위의 요소 꺼내오기
char peek(stack* s) {
	return s->data[s->top];
}

int main() {
	int N;
	cin >> N;

	for (int i = 0; i < N; i++) {
		stack stack;
		string s;
		cin >> s;

		init(&stack); // 초기화

		if (s.length() % 2 == 0) { // 문자열의 길이가 짝수일 때
			// 올바른 괄호 문자열인지 알아본다.
			for (int j = 0; j < s.length(); j++) {
				char c = s[j];

				switch (c) {
				case '(':
					push(&stack, c);
					break;

				case ')':
					if (peek(&stack) == '(')
						pop(&stack);
					else
						push(&stack, c);
					break;
				}
			}
		}

		// 출력
		if (isEmpty(&stack) && s.length() % 2 == 0)
			printf("YES\n");
		else
			printf("NO\n");
	}

	return 0;
}

스택을 사용해서 문제를 풀었다. 스택은 가장 나중에 들어간 요소가 가장 먼저 밖으로 나갈 수 있는 구조를 가지고 있기에 괄호의 짝을 찾는데 적합하다. 가장 밖의 괄호의 '('가 가장 먼저 들어가고, 그 안의 괄호들이 모두 짝은 찾은 뒤 마지막에 그것의 짝인 ')'를 입력받게 되기 때문이다.

 

struct stack {
	char data[51];
	int top;
};

// 초기화
void init(stack* s) {
	s->top = -1;
}

// 삽입 함수
void push(stack* s, int n) {
	s->data[++(s->top)] = n;
}

// 삭제 함수
char pop(stack* s) {
	return s->data[(s->top)--];
}

// 스택이 비어있는지 확인
bool isEmpty(stack* s) {
	return (s->top == -1);
}

// 맨 위의 요소 꺼내오기
char peek(stack* s) {
	return s->data[s->top];
}

스택을 배열로 구현한 코드이다. 'C언어로 쉽게 풀어쓴 자료구조'를 보고 공부해서 구현했다.

 

for (int i = 0; i < N; i++) {
		stack stack;
		string s;
		cin >> s;

		init(&stack); // 초기화

		if (s.length() % 2 == 0) { // 문자열의 길이가 짝수일 때
			// 올바른 괄호 문자열인지 알아본다.
			for (int j = 0; j < s.length(); j++) {
				char c = s[j];

				switch (c) {
				case '(':
					push(&stack, c);
					break;

				case ')':
					if (peek(&stack) == '(')
						pop(&stack);
					else
						push(&stack, c);
					break;
				}
			}
		}

		// 출력
		if (isEmpty(&stack) && s.length() % 2 == 0)
			printf("YES\n");
		else
			printf("NO\n");
	}

괄호문자열을 입력받으면 문자열의 길이를 가장 먼저 확인하게 된다. 만약 문자열의 길이가 홀수라면 어떤 문자열이라고해도 괄호의 짝이 안맞는 것이기에 바로 출력을 하는 부분으로 넘어가게 했다. 문자열의 길이가 짝수라면 for문으로 그 문자열의 길이 만큼 반복하면서 문자열의 문자를 확인한다.

만약 문자가 '('라면 스택에 이를 저장하게끔(push) 했다.

문자가 ')'이라면 스택의 가장 위에 있는 문자가 무엇인지 peek으로 확인한 뒤 '('이라면 자신의 짝을 찾은 것이므로 pop으로 '('을 하나 제거했다. 하지만 '('이 아니라면 스택에 '('을 저장했다.

해당 문자열에 대한 반복이 끝나면 스택이 비어있거나(isEmpty) 문자열이 짝수 길이라면 YES를 그렇지않다면 NO를 출력하게 된다.