4949번 - 균형잡힌 세상

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 {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		char tmp;
		char pop;
		boolean isNo = false;
		while(true) {
			String str = br.readLine();
			if(str.equals(".")) {
				break;
			}
			Stack<Character> stack = new Stack<>();
			for(int i=0;i<str.length();i++) {
				tmp = str.charAt(i);
				if(tmp == '(' || tmp == '[') {
					stack.push(tmp);
				}
				else if(tmp == ')' || tmp == ']') {
					if(stack.isEmpty()) {
						isNo = true;
						break;
					}
					pop = stack.pop();
					if((tmp == ')' && pop == '[') || (tmp == ']' && pop == '(')) {
						isNo = true;
						break;
					}
				}
			}
			if(isNo == false && stack.isEmpty()) {
				sb.append("yes\n");
			} else {
				sb.append("no\n");
			}
			isNo = false;
		}
		System.out.println(sb);
		br.close();
	}
}

palindrome의 변형 중 하나인 괄호 문제입니다. 스택으로 상대적으로 편하게 해결할 수 있습니다.

 

균형 조건은 모든 괄호들이 중간에 미완성된 다른 종류의 괄호 없이 짝지어지는 것이므로

시작 괄호가 나오면 스택에 넣고 끝 괄호가 나오면 스택에서 꺼내서 같은 종류인지 비교해야 합니다.

 

이 때 스택이 비어있는데 끝 괄호가 나오거나 꺼낸 괄호의 종류가 다를 경우 균형을 이루지 않은 것으로 처리하고

 

반복문을 끝냅니다.

 

반복문이 끝나면 끝괄호가 잘못 처리된 적이 없으며 스택이 비어 있는 경우만 yes로 처리하고 나머지를 no로 처리하면 문제가 해결됩니다.