[백준] 9012. 괄호 (JAVA)

이번에 풀어 볼 문제는 <백준 9012번. 괄호>이다.

https://www.acmicpc.net/problem/9012

📌 문제 탐색하기

목표

VPS인지 아닌지 판별하기

해야 할 것

1. VPS를 어떻게 판별할까?

- VPS :  괄호가 순서에 맞게 잘 짝지어져 있는 조합

입력

[첫줄] 테스트 케이스의 수 T

[둘째줄 ~ ] 괄호 문자열 ( 2 ≤ 괄호 문자열의 길이 ≤50)

아이디어

1. VPS를 어떻게 판별할까?

 

1단계. 괄호 문자열을 한 글자씩 탐색하며 스택의 가장 위에 있는 원소와 현재 문자를 비교한다.

2단계. 만약 스택의 가장 위에 있는 원소와 현재 문자가 짝이 맞다면, 가장 위에 있는 원소를 스택에서 제거한다.

3단계. 스택이 비어있거나, 스택의 가장 위에 있는 원소와 현재 문자가 짝이 맞지 않다면, 현재 문자를 스택에 삽입한다.

4단계. 괄호 문자열의 끝까지 1~3단계를 반복했을 때 스택에 남아있는 원소가 없다면, 모두 짝이 맞아 스택에서 제거된 것이므로 VPS로 판별한다. 만약 스택에 남아있는 원소가 있다면 VPS가 아니다. 

 

📌 코드 설계하기

1. input 명령을 받고 스택을 구현한다.

2. 위의 2~4단계를 구현한다.

3. 정답을 출력한다.

📌 정답 코드

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

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        for(int i=0; i<T; i++){
            ArrayDeque<Character> stack = new ArrayDeque<>();
            char[] input = br.readLine().toCharArray();
            boolean isVPS = true;

            for(char c : input){

                if(c==')'){
                   if(!stack.isEmpty()&&stack.peek()=='('){
                       stack.pop();
                   }else{
                       isVPS = false;
                       break;
                   }
                }else{
                    stack.push(c);
                }
            }

            if(!stack.isEmpty()){
                isVPS = false;
            }

            sb.append(isVPS? "YES\n" : "NO\n");
        }

        System.out.println(sb);
    }
}

 

📌 알게 된 것

자꾸 실수하니까 isVPS 처럼 플래그 변수 선언해서 하는 습관을 키우자.