[JAVA] 백준 9012번: 괄호

 

---

문제

• 괄호 문자열이 주어질 때, 모든 여는 괄호에 대해 닫는 괄호가 올바르게 존재하는 VPS(Valid Parenthesis String) 인지 판별하는 문제.

 

아이디어

• [JAVA] 백준 4949번: 균형잡힌 세상 (tistory.com) 문제와 동일하게 풀이를 진행한다.
• 스택을 이용해 여는 괄호를 저장하다가, 닫는 괄호를 만났을 때 여는 괄호가 스택 끝에 존재하는지 체크한다.
• 존재하면 여는 괄호를 pop, 존재하지 않으면 순서가 엇갈린 경우이므로 올바르지 않은 문자열로 취급한다.

 

풀이

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

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        Deque<Character> stack;

        int T = Integer.parseInt(br.readLine());
        for(int t=0; t<T; t++) {
            stack = new ArrayDeque<>();
            String str = br.readLine();
            
            // 입력받은 문자열의 모든 문자에 대해
            loop: for(int i=0; i<str.length(); i++) {
                switch (str.charAt(i)) {
                    // 여는 괄호면 모두 스택에 저장
                    case '(':
                    case '[': {
                        stack.addLast(str.charAt(i));
                        break;
                    }
                    
                    // 닫는 괄호면 스택 끝에 여는 괄호가 있는지 체크
                    case ')': {
                        if(!stack.isEmpty() && stack.peekLast() == '(') {
                            stack.removeLast();
                            break;
                        }
                        // 없으면 올바르지 않은 문자열이므로, 스택에 아무 값이나 넣고 탈출
                        else {
                            stack.addLast('n');
                            break loop;
                        }
                    }
                    case ']': {
                        if(!stack.isEmpty() && stack.peekLast() == '[') {
                            stack.removeLast();
                            break;
                        }
                        else {
                            stack.addLast('n');
                            break loop;
                        }
                    }
                }
            }
            // 스택이 비었다면(정상 종료) VPS
            if(stack.isEmpty()) {
                sb.append("YES").append('\n');
                continue;
            }
            // 스택이 비지 않았다면(정상 종료 실패) Non-VPS
            sb.append("NO").append('\n');
        }

        System.out.println(sb);
    }
}

 

 

채점 결과

9012번 채점 결과

 

문제 링크

• 9012번: 괄호 (acmicpc.net)