[백준] #9012 괄호

🔒문제 설명

괄호가 바르게 구성된 올바른 문자열을 VPS(Valid Parenthesis String) 라고 부릅니다.
한 쌍의 괄호문자열 ()는 VPS입니다.
괄호 안에 VPS를 넣은 (VPS)와 두 VPS를 이어붙인 문자열 역시 VPS입니다.
주어진 문자열이 올바른 문자열 VPS인지 판단하세요.

ex>
“(())()”와 “((()))” 는 VPS 입니다.
“(()(”, “(())()))”, “(()” 는 모두 VPS 가 아닙니다.

🔑해결 아이디어

VPS를 확인하는 방법은 다음과 같습니다.

1. 괄호 문자열 안에서 짝이 맞는 괄호를 삭제합니다.
2. 남은 문자열에 대해서 1.을 다시 반복합니다.
3. 최종적으로 모든 문자열이 사라지면 해당 문자열은 VPS입니다.

예를 들어 "(())()" 문자열의 경우, 두번째 괄호 '('와 세번째 괄호 ')'가 짝이 맞으므로 삭제합니다.
남은 문자열 "()()"에 대해서 첫번째 괄호 '('와 두번째 괄호 ')'가 짝이 맞으므로 삭제합니다.
남은 문자열 "()"가 서로 짝이 맞으므로 삭제합니다.
모든 문자열이 사라졌기 때문에 해당 문자열은 VPS입니다.

즉, 각 여는 괄호 '('에 대해 닫는 괄호 ')'가 적절히 존재한다면 해당 문자열은 VPS입니다.

이를 확인하기 위해 Stack을 사용합니다.
그리고, 위의 확인 과정을 아래와 같이 수정합니다.

1. 문자열을 앞에서 부터 한 글자씩 탐색합니다.
2. 해당 글자가 여는 괄호 '(' 라면 '(' 를 Stack에 추가합니다.
3. 해당 글자가 닫는 괄호 ')'라면 다음의 과정을 따릅니다.
   3-1. Stack 안에 '(' 가 존재한다면, 괄호의 짝이 맞으므로 Stack안의 '('를 삭제합니다.
   3-2. Stack 안에 '('가 존재하지 않는다면, ')'의 짝이 맞지 않으므로 해당 글자는 VPS가 아닙니다.
4. 모든 과정이 끝난 후 Stack이 비어 있다면 모든 괄호가 짝이 맞아 삭제 된 것이므로 해당 문자열은 VPS입니다.

💻소스코드

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

public class BJ9012 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int TestCase = Integer.parseInt(sc.nextLine());


        for(int i = 0; i<TestCase; i++){
            String VPS = sc.nextLine();
            int Answer = 1;
            Stack<Character> stack = new Stack<>();
            for(int j = 0; j<VPS.length(); j++){
                if(VPS.charAt(j) == '('){;
                    stack.push('(');
                }
                else{
                    if(stack.isEmpty()){
                        Answer = 0;
                        break;
                    }
                    else{
                        stack.pop();
                    }
                }
            }

            if(stack.isEmpty() == true && Answer == 1)
                System.out.println("YES");
            else
                System.out.println("NO");
        }
    }
}