4949번: 균형잡힌 세상

문제

어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 작성하는 문제입니다. 문자열에 포함되는 괄호는 소괄호 () 와 대괄호 [] 로 2종류입니다.

• 모든 왼쪽 소괄호(()는 오른쪽 소괄호())와만 짝을 이뤄야 합니다.
• 모든 왼쪽 대괄호([)는 오른쪽 대괄호(])와만 짝을 이뤄야 합니다.
• 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재해야 합니다.
• 모든 괄호들의 짝은 1:1 매칭만 가능합니다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않습니다.
• 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 합니다.
• 입력: 각 문자열은 영문 알파벳, 공백, 소괄호, 대괄호 등으로 이루어져 있으며, 마지막 글자를 온점(.)으로 끝납니다. 입력의 종료조건으로 맨 마지막에 온점 하나(.)가 들어옵니다.
• 출력: 각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력합니다.

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

풀이: 스택

여러 종류의 괄호가 등장하므로 스택(Stack) 자료구조의 LIFO(Last In First Out) 특성을 활용하여 가장 최근에 열린 괄호부터 짝을 맞추는 전형적인 문제입니다. 

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));

       while (true) {
          String s = br.readLine();
          
          // 입력 종료 조건
          if (s.equals("."))
             break;

          Stack<Character> st = new Stack<>();
          
          for (char c : s.toCharArray()) {
             // 1. 열린 괄호는 스택에 삽입
             if (c == '(' || c == '[') {
                st.push(c);
             } 
             // 2. 닫힌 소괄호 검사
             else if (c == ')') {
                if (!st.isEmpty() && st.peek() == '(') {
                   st.pop(); // 짝이 맞으면 제거
                } else {
                   st.push(c); // 짝이 맞지 않으면 닫힌 괄호를 그대로 삽입 (영원히 남게 됨)
                }
             } 
             // 3. 닫힌 대괄호 검사
             else if (c == ']') {
                if (!st.isEmpty() && st.peek() == '[') {
                   st.pop();
                } else {
                   st.push(c);
                }
             }
          }

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

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

알고리즘 분류

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