[Java11] 백준 4949번 : 균형잡힌 세상

링크텍스트

랜덤한 문자열에서 열린 괄호가 쌍을 이루어 정상적으로 닫혔는지 확인하는 문제이다.

다른 문자들은 신경쓰지 말고 열린 괄호를 읽으면 이를 push하고 닫힌 괄호를 읽으면 pop하여 비교하면된다. 만약 pop한 결과가 해당 괄호와 매칭된다면 계속하고, 매칭되는 값이 아니라면 종료하게 하여 반복문이 종료되었을 때 반복문이 반복한 횟수와 문자열의 길이를 비교하여 yes인지 no인지 판단하였다. 추가로 모든 괄호가 닫혔는지 확인해야하므로 empty로 스택에 남은 열린 괄호가 있는지 확인하는 과정이 yes를 출력할때 필요하다.

처음 제출하였을때 틀렸습니다 판정을 받았는데 괄호가 다 짝을 이룬지를 empty로 확인하지 않고 문자를 다 읽었는지만 확인하여 발생한 문제였다. 예를 들어 (((만 입력했을때 no가 출력되어야 하지만 스택에 그대로 쌓여있고 이에 대한 비교를 한번도 하지 않아 정상적으로 모든 문자열을 읽고 yes가 출력된다. empty로 스택이 비었는지 확인하여 해결하였다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Baekjoon_4949 {
  static class Stack {
    static class Node {
      private final int data;
      private Node next;

      public Node(int data) {
        this.data = data;
        this.next = null;
      }
    }

    private Node head;
    private int size;

    public Stack() {
      head = null;
      this.size = 0;
    }

    public void push(int data) {
      Node newNode = new Node(data);
      newNode.next = head;
      head = newNode;
      size++;
    }

    public int pop() {
      if (head == null) return -1;
      int result = head.data;
      head = head.next;
      size--;
      return result;
    }

    public int empty() {
      return size == 0 ? 1 : 0;
    }
  }

  public void result() throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력받기
    while (true) {
      Stack stack = new Stack();
      String str = br.readLine();
      if (str.equals(".")) break; // 종료 조건

      int i;

      for (i = 0; i < str.length(); i++) {
        char c = str.charAt(i);
        if (c == '(' || c == '[') {
          stack.push(c);
        } else if (c == ')') {
          if (stack.pop() != '(')
            break;
        } else if (c == ']') {
          if (stack.pop() != '[')
            break;
        }
      }
      if (i == str.length() && stack.empty() == 1) System.out.println("yes");
      else System.out.println("no");
    }
    br.close();
  }

  public static void main(String[] args) throws Exception {
    new Baekjoon_4949().result();
  }
}