[백준] 9012번 괄호(JAVA)

문제

- 괄호 문자열은 두 개의 괄호 기호인 '('와 ')'만으로 구성되어 있는 문자열

- 한 쌍의 괄호 기호로 된 "()" 문자열은 기본 VPS(Valid Parenthesis String, 올바른 괄호 문자열)

- 만일 x가 VPS라면 "(x)"도 VPS

- 두 VPS x와 y를 접합시킨 새로운 문자열 xy도 VPS

- 주어진 괄호 문자열이 VPS인지 아닌지 판단해서 결과를 YES / NO로 출력

 

해결방법

스택에 괄호를 넣으면서 VPS를 판단할 수 있도록 하였다. 비어있는 상태에서 닫힌 괄호가 입력되면 VPS가 아니므로 NO를 출력할 수 있도록 하였고, 비어있는 상태에서 열린 괄호가 입력되면 스택에 넣어주었다. 그리고 스택에 무언가 들어있는 상태에서 열린 괄호가 입력되면 스택에 넣어주고, 닫힌 괄호가 입력되면 스택에서 하나 빼내어 짝이 되는지 확인할 수 있도록 하였다. 만약, 짝이 안맞으면 NO를 출력할 수 있도록 하였다. 마지막에 다 입력되고 스택이 비어있지 않으면 닫힌 괄호가 개수에 맞게 입력된 것이 아니므로 NO를 출력할 수 있도록 하였다.

 

코드

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

class Main {

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

        for(int i = 0; i<N; i++){
            String s = br.readLine();
            Stack<Character> stack = new Stack<>();
            String result = "YES";

            for(int j = 0; j<s.length(); j++){
                char c = s.charAt(j);
                // 스택이 비었다면
                if(stack.isEmpty()){
                    // 스택이 빈 상태에서 닫힌 괄호가 입력되면 VPS NO
                    if(c == ')') {
                        result = "NO";
                        break;
                    }
                    // 열린 괄호가 입력되면 스택에 push()
                    stack.push(c);
                }
                // 스택이 비지 않았다면
                else{
                    if(c == '(') stack.push(c);				// 열린 괄호가 입력되면 push()
                    if(c == ')'){					// 오른쪽 소괄호라면
                        char before = stack.pop();			// 이전 것 pop()
                        if(before != '(') result = "NO";		// 이전 것이 짝이 맞지 않으면 VPS NO
                    }
                }
            }
            
            // 모든 것이 입력이 끝났는데 스택에 남은 것이 있다면 VPS NO
            if(!stack.isEmpty()) result = "NO";
            
            System.out.println(result);
        }
        br.close();
    }
}