1. Problem 📃

[ 괄호 ]

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 로 나타내어야 한다.

2. Input 📇

[ 입력 ]

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

3. Output 📠

[ 출력 ]

출력은 표준 출력을 사용한다.
만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다.

4. Example 📚

[ 입출력 예시 ]

5. Solution 🔑

한 쌍의 '('   ')' 이므로 정수형 변수 하나를 두고 열면 ++, 닫을 때 --하면서 풀 수 있지만 스택을 이용하란 문제이므로 스택을 이용하여 풀었다.


1. 몇 개의 테스트 케이스(T)를 받을지 입력받는다.
스택(PS)를 선언하고 T만큼 루프를 돌면서 문장 하나하나 검사해준다.


2. 우선 문장이 완벽한 괄호가 맞다는 전제로 result값을 "YES"로 지정한다.
괄호 문장을 읽어들여 한 문자 한 문자 검사한다.


3. 여는 문자면 스택에 push해주고, 만약 닫는 문자일 때, 스택이 비어있다면 result값을 "NO"로 바꾸어 break;하여 다음 문장을 검사한다. 비어있지 않다면 PS의 값을 pop해준다.


4. 문장을 다 검사하고 스택(PS)이 비어있지 않다면 result를 "NO" 값으로 변경하고 최종적인 result값을 StringBuilder(sb)에 추가하고 개행문을 추가한다.


5. 최종적으로 StringBuilder(sb)에 담긴 값을 출력해준다.

6. Code 💻

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();
		
		Stack<Character> PS = new Stack<Character>();

		int T = Integer.parseInt(br.readLine());
		
		for(int i=0; i<T; i++) {
			PS.clear();
			String result = "YES";
			String str = br.readLine();
			
			for(int j=0; j<str.length(); j++) {
				if(str.charAt(j) == '(') {
					PS.push(str.charAt(j));
				}
				else {
					if (PS.empty()) {
						result = "NO";
						break;
					}
					PS.pop();
				}
			}
			if(!PS.empty()) {
				result = "NO";
			}
			sb.append(result + "\n");
		}
		System.out.println(sb.toString());
	}

}