[JAVA] 백준 9012번 【괄호】

---

위 문제는, Stack 클래스를 사용해서 풀어도 된다.

 

근데, 문제를 잘 이해하고, Stack 데이터 구조를 잘 알 고 있으면 굳이 Stack을 사용하지 않아도 풀린다.

 

나같은 경우는 Stack을 사용하지 않았다...ㅎ

 

먼저 VPS 가 될 수 있는 조건은 괄호가 짝을 이뤄야 하고, 감쌀 수 있는 형태로 입력되야 한다는 것이다.

 

 

 

규칙 1.

 

[  () () (   ]  의 경우 괄호가 짝을 이루지 못하므로 VPS가 아니다.

 

규칙 2.

 

[ () () )(  ]  의 경우 괄호의 갯수는 짝을 이루지만, )( 가 감쌀 수 없는 형태이므로 VPS 가 아니다.

 

 

 

 

이 규칙을 생각해서,

 

초기값 0으로 지정한 변수를,  " ( " 가 입력되면 +1 을 하고 " ) " 가 입력되면 -1을 하도록 하고

 

최종 값이 0이 되면 괄호가 짝을 이룬다는 것을 알 수 있다.

 

 

하지만, ")" 가 먼저 입력되는 경우를 처리해야한다.

 

위 상황은, 입력될때마다 +1 -1 되는 변수의 누적 합이 -1이 되는 순간 ")" 가 먼저 들어오는 상황임을 알 수 있다. 

 

 

즉, 변수가 +1,-1 연산이 이루어지는 동안 음수가 되지 않으며 최종 값이 0 인 경우 VPS 임을 판단할 수 있다.

 

 

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 N = Integer.valueOf(br.readLine());
        
        for (int i = 1; i <= N; i++) {
            if (isVPS(br.readLine())) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }

    static boolean isVPS(String input) {
        int result = 0;
        for (int i = 0; i < input.length(); i++) {
            if (input.charAt(i) == '(') {
                result++;
            } else if (input.charAt(i) == ')') {
                result--;
            }
            if (result == -1) { //규칙 2를 어김
                return false;
            }
        }
        return result == 0;
    }
}