[Java] baekjoon_4949 : 균형잡힌 세상

자료 구조, 문자열, 스택

균형잡힌 세상 : Silver4

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

4949번: 균형잡힌 세상

 

 

이전에 포스팅한 괄호 문제와 비슷한 것 같아 참고해서 풀어보았다.

 

https://la-reveuse.tistory.com/403

[Java] baekjoon_9012 : 괄호

 

 

풀이

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

public class Main22 {
  private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

  public static void main(String[] args) throws IOException {
    String str = "";
    while (!(str = br.readLine()).equals(".")) {
      bw.write(isBalanced(str));
    }
    br.close();
    bw.close();
  }

  private static String isBalanced (String str) {
    Stack<Character> stack = new Stack<>();

    for (int i = 0; i < str.length(); i++) {
      char ch = str.charAt(i);
      if (ch == '(' || ch == '[') {
        stack.push(ch);
      } else if (ch == ')' || ch == ']') {
        if (stack.isEmpty()) {
          return "no\n"; // 여는 괄호 없이 닫는 괄호가 나올 경우
        }
        char top = stack.pop();
        if (!((top == '(' && ch == ')') || (top == '[' && ch == ']'))) {
          return "no\n"; // 괄호 쌍이 매칭되지 않는 경우
        }
      }
    }

    if (stack.isEmpty()) {
      return "yes\n"; // 괄호가 쌍을 이룸
    } else {
      return "no\n"; // 여는 괄호가 남아있음
    }
  }
}

 

ㄴ 여기서 isBalanced 함수는 문자열을 받아 괄호 균형을 판단하도록 정의했다.
ㄴ Stack 자료구조를 사용하여 여는 괄호를 만날 때마다 스택에 추가하고, 닫는 괄호를 만날 때마다 스택에서 꺼내어 짝이 맞는지 확인한다.
ㄴ 스택이 비어있는데 닫는 괄호가 나오면 "no"를 반환한다. (여는 괄호가 남아있을 때)
ㄴ 꺼낸 괄호와 현재 닫는 괄호가 서로 짝이 맞지 않으면 "no"를 반환한다.
ㄴ 문자열을 모두 확인한 후에도 스택이 비어있으면 "yes"를 반환한다. (모든 괄호가 쌍을 이룸)

 

=> 예를 들어, "([])"와 같은 문자열은 괄호 균형을 이루기 때문에 "yes"가 출력되지만, "(]"나 "([)]"와 같은 문자열은 균형이 깨져 "no"가 출력된다.