[백준] 9012. 괄호 - 실버4

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

9012번: 괄호

 

문제 요약

한 쌍의 괄호 기호로 된 "()" 문자열을 VPS라고 부른다. 입력으로 주어진 괄호 문자열이 VPS인지 아닌지를 판단해서 그 결과를 YES와 NO로 나타낸다.

 

문제 해결 아이디어

stack을 이용한다. stack이 비어있으면 무조건 넣고, 비어있지 않을 때에는 stack.peek(), 즉 가장 최근에 들어간 괄호가 현재 괄호와 같은지 확인 후 같으면 넣고, 아니면 뽑는다. 

여기까지 생각했는데 틀렸다!

반례가 있다. ( ) 이 경우에는 뽑는 게 맞는데, ) ( 이 경우가 있을 수 있다. 그래서 따로따로 생각해 줬다. 이런 반례 하나하나에 조건 걸어 줘서 구질구질해지는 코드를 별로 안 좋아하는데 나는 아직 잘 못하니까 어쩔 수 없다..

 

완성된 코드

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

public class Main_BOJ_9012_괄호 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(br.readLine());

		Stack<Character> stack = new Stack<>();

		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			char[] input = str.toCharArray();
			// 비어있을 때: 무조건 넣기
			// 비어있지 않을 때: peek이 같은지 확인 후 같으면 넣고 아니면 뽑기
			// 다르다는 게 () 이럴때는 뽑는게 맞는데 )( 이럴 경우가 있으니까 체크해 줘야 한다
			for (int j = 0; j < input.length; j++) {
				if (stack.isEmpty()) {
					stack.push(input[j]);
					continue;
				}

				else {
					if (stack.peek().equals(input[j]))
						stack.push(input[j]);
					else if (stack.peek() == '(' && input[j] == ')') {
						stack.pop();
					} else
						stack.push(input[j]);
				}
			}

			if (!stack.isEmpty())
				sb.append("NO");
			else
				sb.append("YES");
			sb.append("\n");
			stack.clear();
		} // end of for
		System.out.println(sb);
	} // end of main
} // end of class