백준 9012 (괄호)

문제

---

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다. 

 

풀이

---

stack 을 이용하여 '(' 일경우 push 하고 ')' pop 하는 방식으로 풀었고 pop 시에 이미 stack 이 비어있으면 false 값을 return  했다. 또 검사 가 끝났는데 stack 이 비어있지 않으면 '(' 개수보다 ')' 개수가 더 적은 것이므로 false 값을 return 하였다. 

 

 

<코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {	
	
	public static void main(String[] args) throws IOException{
		
		int n;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		n = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < n ; i++) {
			String line = br.readLine();
			
			if(check(line)) {
				sb.append("YES").append("\n");
			}
			else {
				sb.append("NO").append("\n");
			}
		}
		
		System.out.println(sb);
	}
	
	static boolean check(String line) {
		
		Stack st = new Stack();
		
		for(int i = 0 ; i < line.length() ; i++) {
			if(line.charAt(i) == '(') {
				st.push(line.charAt(i));
			}
			else if(line.charAt(i) == ')'){
				if(st.empty()) {
					return false;
				}
				
				st.pop();
			}
		}
		
		if(!st.empty()) {
			return false;
		}
		
		return true;
	}
}