백준 9012번
https://www.acmicpc.net/problem/9012

---

문제

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

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

---

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.

---

생각하기

동작
동작 방법은 Stack구조를 이용해서 풀어냈다.

방법은 간단하다.

• '(' 가 들어올 경우 stack.push()를 진행하고,
• ')' 일 경우에는 stack.pop() 을 한다.

만약 )가 먼저 들어올 경우 바로 "NO" 처리를 해주면 되기 때문에
stack의 size를 구해서 size 값이 0일 경우에는 VPS의 균형자체가 맞지 않아서 뒤에 들어오는 괄호는 볼 것도 없이 NO이다.
때문에 stack.push()를 해주고 바로 break를 걸어주면 반복문을 빠져나가서 "NO"가 출력된다.

NO와 YES를 출력하게 되는 조건은
stack이 비어있는지의 여부를 통해서 판별한다. VPS가 맞을 경우는 stack이 비어있을 것이기 때문에 YES를 출력하지만

VPS가 맞지 않을 경우는 stack이 비어있지 않기 때문에 NO를 출력하게 된다.

TMI

백준 4949번의 균형잡힌 세상과 거의 똑같은 문제였다.

이전 문제에서 고생을 했던 탓인지 쉽게 풀었다.

그때 문제를 풀었던 당시 Stack구조를 이용해서 풀고 싶었는데,
이번에는 Stack 구조를 이용해서 풀 수 있어서 뿌듯하다.

---

코드

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		Stack<Character> stack = new Stack<>();

		for(int i=0; i<N; i++) {
			String str = br.readLine();
			int length = str.length();

			for(int j=0; j<length; j++) {
				char ch = str.charAt(j);
				
				if(ch == '(') {
					stack.push(ch);
				}
				else {
					int size = stack.size();
					if(size == 0) {
						stack.push(ch);
						break;
					}
					else {
						stack.pop();
					}
				}
			}

			if(stack.isEmpty()) {
				System.out.println("YES");
			}
			else {
				System.out.println("NO");
			}

			stack.clear();
		}
	} // End Main
} // End Class