[BOJ] 백준 9012번: 괄호

www.acmicpc.net/problem/9012

9012번: 괄호

괄호 '(' 와 ')' 가 주어졌을 때 ( )는 올바른 문자열이며 올바른 문자열 S에 대하여 ( S ) 도 올바른 문자열이고, 올바른 문자열 T와 ST를 이루는 것도 올바른 문자열일 때, 주어진 괄호 문자열이 올바른 문자열인지 판별하는 문제입니다.

문자열을 탐색하는 중 현재 문자가 ( 라면, 이 후 가장 먼저오는 )와 짝을 이뤄야합니다.

Last in First out 의 특징을 갖는 스택 자료구조를 사용하면 해결 할 수 있습니다.

문자열이 아래와 같이 주어진다면 다음 과정과 같이 올바른 괄호열인지 판정할 수 있습니다. 

현재 문자열이 '(' 라면 스택에 넣어줍니다. 0번과 1번 문자가 스택에 들어갔습니다.

현재 문자열이 ')' 라면 스택이 비어있는지 확인하고, 가장 마지막에 들어간 '(' 를 제거합니다.

만약 스택이 비어있는 상태에서 ')'가 있다면 ( ( ) ) ) 와 같은 올바르지 못한 괄호열이므로 과정을 중단합니다. 

그렇지 않다면 가장 마지막에 들어간 '(' 와 현재 문자열 ')' 이 올바른 괄호문자열을 이룬것입니다.

 

3번째와 4번째도 동일하므로 

5번째 문자는 ')' 이며, 이는 0번째 '(' 문자와 올바른 괄호열을 이룹니다.

만약 ( ( ) 와 같은 문자열이 온다면 탐색 종료 후 괄호쌍을 이루지 못한 0번째 '(' 가 스택에 남아있으므로 탐색 종료 후 스택이 비어있는 경우에만 올바른 괄호열이 됩니다.

이를 코드로 나타내면 아래와 같습니다.

int flag = 1; 
// flag가 1이면 올바른 괄호열
// 0이면 올바르지 못한 괄호열
for (auto ch : str) {
	if (ch == '(') {
		s.push(ch);
	}
	else {
		if (!s.empty()) {
			s.pop();
		}
		else {
			flag = 0;
			break;
		}
	}
}
if (flag && s.empty()) {
	flag = 1;
}
else {
	flag = 0;
}

cout << (flag ? "YES\n" : "NO\n");

 

괄호쌍을 이루지 못한 ( 의 개수를 카운트하면 스택을 사용하지 않고 해결할 수 있습니다.

int o = 0;
int flag = 1;
for (auto ch : str) {
	if (str[i] == '(') {
		o += 1;
	}
	else {
		if (o) {
			o -= 1;
		}
		else {
			flag = 0;
		}
	}
}
o = (!o ? 1 : 0);
cout << (o * flag ? "YES\n" : "NO\n");