[백준 알고리즘] 9012번 : 괄호

문제

9012번 : 괄호

9012번: 괄호

내가 작성한 코드 (C++ 성공)

#include <iostream>
#include <string.h>
#include <string>

using namespace std;

int main(){
	int t;
	cin >> t;
	
	string ps;
	char stack[51];
	
	for(int i=0; i<t; i++){
		cin >> ps;
		int index = 0;
		bool check = true;
		
		for(int j=0; j<ps.length(); j++){
			if(ps[0] == ')'){
				check = false;
				break;
			}
			if(ps[j] == '(') {
				stack[index] = ps[j];
				index++;
			} else if (ps[j] == ')'){
				index--;
				if(index < 0) {
					check = false;
					break;
				}
			}
			/*
			for(int k=0; k<index; k++){
				cout << stack[k] << " ";
			}
			cout << "\n";
			*/
		}
		
		if(index > 0) check = false;
		
		if(check) cout << "YES\n";
		else cout << "NO\n";	
	}

	return 0;
}

 

정리

이 문제는 얼핏보면 간단한 문제처럼 보인다.
하지만, 이 문제에서 중요한 점은 예외처리를 잘 해주어야 한다는 점이다.

그래서 생각한 예외가 몇가지 있었다.

1) 처음에 ')' 가 올 수 없다. 그리고 당연히 마지막에 '(' 가 와서는 안된다.
2) 합계를 통해 구할 수 없는 경우도 있다.
3) 같은 갯수의 여는 괄호와 닫는 괄호가 있다고 해도 짝이 맞지 않을 수 있다.

내가 작성한 예외 말고도 다른 예외도 있을 수도 있다.
이런 예외를 제외하고 문제를 풀 수 있었다.
결론은 스택을 이용해서 문제를 풀어보았다.

스택을 이용해서
'(' 인 여는 괄호가 들어가고
')' 인 닫는 괄호가 나오게 되면 
'(' 인 괄호를 스택 배열에서 제거해주었다.

이런 방법을 통해 결과적으로 스택에 아무것도 들어있지 않다면 올바른 괄호가 사용된 것이기 때문에 "YES"
그렇지 않다면 올바르지 않은 괄호가 사용되었기 때문에 "NO"