9012번: 괄호

문제

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열입니다. 그중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부릅니다. 입력으로 주어진 괄호 문자열이 VPS인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내는 문제입니다.

• 입력: 첫째 줄에 테스트 데이터의 수를 나타내는 정수 T가 주어집니다. 각 테스트 데이터는 한 줄로 구성된 괄호 문자열입니다. (길이는 2 이상 50 이하)
• 출력: 각 테스트 데이터에 대해 VPS면 YES, 아니면 NO를 한 줄에 하나씩 출력합니다.

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

풀이: 스택

단일 종류의 괄호만 등장하므로, 스택(Stack)을 활용하여 짝을 맞추는 전형적인 문제입니다.

1. 스택 선언: 각 테스트 케이스(문자열)를 검사할 때마다 새로운 Stack을 생성합니다.
2. 문자열 순회 및 짝 맞추기: 문자열을 한 글자씩 순회합니다.
   • 열린 괄호 (를 만나면 스택에 삽입(push)합니다.
   • 닫힌 괄호 )를 만났을 때, 스택의 맨 위(peek)에 짝이 맞는 열린 괄호가 있다면 스택에서 제거(pop)합니다.
   • 만약 스택이 비어있거나 짝이 맞지 않는다면, 닫힌 괄호 자체를 스택에 삽입(push)합니다.
3. 결과 판별: 짝이 맞지 않는 닫힌 괄호가 스택에 한 번 들어가면 그 위로 어떤 문자가 오더라도 다시는 pop으로 꺼낼 수 없게 됩니다. 따라서 문자열 탐색이 끝난 후 스택이 비어있는지(st.isEmpty()) 단 하나의 조건만 확인하면 문자열의 올바른 괄호 여부를 판별할 수 있습니다.

코드

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

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

       int t = Integer.parseInt(br.readLine());
       
       while (t-- > 0) {
          String s = br.readLine();
          Stack<Character> st = new Stack<>();
          
          for (char c : s.toCharArray()) {
             // 1. 열린 괄호는 스택에 삽입
             if (c == '(') {
                st.push(c);
             } 
             // 2. 닫힌 괄호를 만났을 때, 스택 맨 위가 열린 괄호라면 짝을 지어 제거
             else if (!st.isEmpty() && st.peek() == '(') {
                st.pop();
             } 
             // 3. 짝이 맞지 않으면 닫힌 괄호를 그대로 삽입 (영원히 남게 됨)
             else {
                st.push(c);
             }
          }

          // 탐색이 끝난 후 스택이 완전히 비워졌을 때만 YES
          bw.write((st.isEmpty() ? "YES\n" : "NO\n"));
       }

       bw.flush();
       bw.close();
       br.close();
    }
}

알고리즘 분류

자료구조 (Data Structures), 스택 (Stack), 문자열 (String)