백준 4949번. 균형잡힌 세상 (Java)

Problem

• 문제 링크

괄호가 균형을 제대로 이루는지 확인하는 문제입니다.

Solution

간단한 짝 맞추는 문제입니다.

문제 조건이 복잡해 보이지만 결론은 여는 괄호와 닫는 괄호의 쌍이 일치하는 지 확인하라는 문제입니다.

Stack 자료구조를 이용해서 풀 수도 있고, 간단히 char[] 배열과 cursor 를 이용하여 해결 할 수도 있습니다.

여는 괄호가 들어오면 스택에 넣어두고, 닫는 괄호를 만나면 스택에서 하나 꺼냅니다.

스택에서 꺼낸 여는 괄호와 짝이 맞다면 계속해서 진행하고, 스택이 비어있거나 짝이 맞지 않으면 중지합니다.

속도는 배열을 쓴게 더 빠릅니다.

Java Code 1

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

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

        while (true) {
            String input = br.readLine();

            if (input.equals(".")) {
                bw.flush();
                return;
            }

            bw.write(isBalanced(input));
        }
    }

    // use Stack
    static String isBalanced(String s) {
        Stack<Character> stack = new Stack<>();
        boolean result = true;

        for (char one : s.toCharArray()) {
            if (one == '(' || one == '[') {
                stack.push(one);
            } else if (one == ')') {
                if (stack.isEmpty() || stack.pop() != '(') {
                    result = false;
                    break;
                }
            } else if (one == ']') {
                if (stack.isEmpty() || stack.pop() != '[') {
                    result = false;
                    break;
                }
            }
        }

        if (!stack.isEmpty()) {
            result = false;
        }

        return result ? "yes\n" : "no\n";
    }
}

Java Code 2

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

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

        while (true) {
            String input = br.readLine();

            if (input.equals(".")) {
                bw.flush();
                return;
            }

            bw.write(isBalanced(input));
        }
    }

    // use char[] array and cursor
    static String isBalanced(String s) {
        char[] stack = new char[s.length()];
        int cursor = 0;
        boolean result = true;

        for (char one : s.toCharArray()) {
            switch (one) {
                case '(':
                case '[':
                    stack[cursor++] = one;
                    break;
                case ')':
                    if (cursor == 0 || stack[--cursor] != '(') {
                        return "no\n";
                    }
                    break;
                case ']':
                    if (cursor == 0 || stack[--cursor] != '[') {
                        return "no\n";
                    }
                    break;
            }
        }

        if (cursor > 0) {
            result = false;
        }

        return result ? "yes\n" : "no\n";
    }
}