백준 코딩 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 이하이다. 

출력

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

 

 

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));
        int num = Integer.parseInt(br.readLine());
        Stack<Character> parenthesis = new Stack<>();
                 
        for (int i = 0 ; i < num; i++) {
            parenthesis.clear(); 
            //이전 테스트케이스의 Stack에 남아있는 요소가 있을 수 있기 때문에 새로운 테스트 케이스를 시작하기 전에 Stack을 비워준다.
            char[] arr = br.readLine().toCharArray();
            //입력한 문자열을 char[]배열로 전환한다.
            for (int j = 0 ; j < arr.length; j++) {
                parenthesis.push(arr[j]);
            }//char[]배열의 각 요소를 stack에 집어넣는다.
            
            String isVps = null; // VPS인지 아닌지 문자열 선언
            int vps = 0; // ')'이면 vps++   '('이면 vps--
            boolean vpsFlag = true; // 하나의 VPS가 완성되면 ()를 상쇄된 걸로 가정하고 true 그 이외의 경우는 false
            while (!parenthesis.isEmpty()) { // Stack이 모두 비워질때까지 반복문 수행
                char temp = parenthesis.pop(); // stack의 맨 위 요소를 꺼낸다.
                if (temp == '(' && vpsFlag == true) {//처음에 '('가 나와버리면 애초에 VPS 성립이 안되므로 break시킨다.
                    vps--;
                    vpsFlag =false;
                    break;
                } else if (temp == ')' && vpsFlag == true) {//true는 아무것도 없는 상태로 간주.
                    vps++;
                    vpsFlag = false;
                } else if (temp == '(' && vpsFlag == false) {// ')'가 나오고 이후에 '('가 나온경우
                    vps--;
                    if (vps == 0) { // false인 상태에서 VPS가 완성되어 ()가 모두 상쇄된 경우
                        vpsFlag = true;
                    }
                } else {
                    vps++;
                }                
            }
            if (vps == 0 && vpsFlag == true) { // 괄호 문자열이 모두 완성되어 모두 상쇄된 상태
                isVps = "YES"; 
            } else { 
                isVps = "NO";
            }
            System.out.println(isVps);
        }
    }
}

 

결과화면