Solution

import java.util.Scanner;

public class BackJoon9012 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        sc.nextLine();

        String[] str = new String[T];

        for (int i = 0; i < T; i++) {
            str[i] = sc.nextLine();
        }

        for (String s : str) {
            int leftCnt = 0;
            int rightCnt = 0;
            Boolean isVPS = true;

            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') {
                    leftCnt++;
                } else if (s.charAt(i) == ')'){
                    rightCnt++;
                }

                if (leftCnt < rightCnt) {
                    isVPS = false;
                    break;
                }

            }

            if (leftCnt != rightCnt) {
                isVPS = false;
            }

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

생각보다 쉽게 푼 문제이다.
왼쪽, 오른쪽 괄호의 개수가 같아야하고, 다 검사하기 전에 오른쪽 괄호의 개수가 더 크면 VPS가 아니다.
조건을 위와 같이 걸고 반복문으로 문자열을 검사하기만 하면된다.

+

Stack을 사용하면 더 간단하게 구현이 가능했다!
"(" 가 들어올때는 Push하고 ")" 가 들어올때는 Pop 한 뒤 스택이 모두 비워졌고 checkFlag(괄호의 짝이 맞는지 안맞는지 체크) 가 트루일 때 YES 아닐때는 NO 하면 된다.

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        sc.nextLine();

        String[] str = new String[T];

        for (int i = 0; i < T; i++) {
            str[i] = sc.nextLine();
        }

        for (int i = 0; i < str.length; i++) {
            Stack stack = new Stack();
            boolean checkFlag = true;

            for (String s : str[i].split("")) {
                if (s.equals("(")) {
                    stack.push(s);
                } else {
                    if (stack.isEmpty()) {
                        checkFlag = false;
                        break;
                    } else {
                        stack.pop();
                    }
                }
            }

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