[BOJ] 4949번: 균형잡힌 세상 (Java)

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

 

---

 

이 문제는 소괄호와 대괄호가 짝이 맞게, 올바른 순서로 이루어져 있는지 확인하는 문제다.

처음 문제를 접했을 때, 주어진 문장을 한 글자씩 검사하여 괄호가 등장하면 큐나 덱에 push하고 그 후 괄호가 잘 구성되어 있는지 검사하려 했다.

 

시도 1) 큐에 괄호들 push 후 큐 검사

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;

public class BOJ_4949_1 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String st = "";
        ArrayList<String> result = new ArrayList<>();

        // . 입력 전까지 문자열 입력
        do {
            st = br.readLine();
            Deque<Character> sentence = new ArrayDeque<>();

            if(st.equals("."))
                break;

            else {
                for (char c : st.toCharArray()) {
                    if (c == '(' || c == ')' || c == '[' || c == ']' || c == '.')
                        sentence.add(c);
                }
            }
            result.add(checkBalance(sentence));

        } while(true);

        while (!result.isEmpty())
            System.out.println(result.remove(0));
    }

    static String checkBalance(Deque<Character> dq) {
        char first, second = ' ';
        int count = 0;

        do {
            first = dq.poll();

            if(first!='.') second = dq.peek();

            if(((first=='(' && second==')') || (first=='[' && second==']'))){
                second = dq.poll();
            }

            else {
                dq.add(first);
            }

            if (dq.size() == 3)
                count++;

            if (count == 4) break;

            if (dq.size() == 1 && dq.peek() == '.') break;

        } while(true);

        if (dq.size() == 1) return "yes";

        else return "no";
    }
}

 

코드가 딱 봐도 길다...

 

처음에 내가 코드를 짠 기준은 다음과 같았다.

우선 문장에는 .도 함께 포함된다.

가장 첫 요소를 pop()하고 두 번째 것을 peek()하여 비교했을 때 ( 와  ) 혹은 [ 와 ] 로 짝이 맞는다면 두 번째 것도 역시 pop을 해준다. 하지만 pop한 첫 번째 요소가 다음 요소와 짝이 맞지 않는다면, 첫 번째 것을 제일 뒤로 add 해준다.

 

이러한 과정을 큐에 . 만 남고 괄호가 모두 pop 되어 없어질 때까지 반복한다.

백준 사이트에서 제공된 예제 입력을 콘솔창에 입력했을 때 예제 출력대로 결과가 잘 나와 사실 정답인 줄 알았다...

하지만 

 

틀렸다!

 

왜일까? 곰곰이 생각해보았다.

 

---

 

 

<개선점> 괄호의 순서, 구성이 잘못된 경우를 제대로 처리하지 않는다.

불필요한 count 변수를 사용하고 있는 게 문제이다. 일단, 괄호를 pop하고 add하는 걸 계속 반복만 하고 더 이상 괄호가 빠지지 않는다면 불균형적인 괄호 문장으로 판단하여 반복문을 break하고 결과를 "no"로 저장되게끔 하였다. 이 일정 이상의 반복의 기준을 count로 설정했다. 예를 들어  )(. 와 같은 문장이 있을 때, 큐의 길이는 .을 포함해 3이고 이때 pop&add가 4번이나 반복 되어 count++이 총 4번 반복 되면, 이 이상 반복해도 큐에서 빠지는 괄호가 없기에 같은 과정이 반복되기만 하는 불균형 문장으로 판단할 수 있다. 얼핏 보면 괜찮다고 생각했는데, 이 당시에 저 예시에 홀린 것인지... '큐 길이가 3인 상태가 4번이나 반복되면 불균형 문장!' <- 이렇게 생각하며 논리의 오류를 남발했다... 허허

 

하지만 우리는 ( [ ) ] 와 같은 불균형적인 괄호 문장도 판단해내야한다. 

지금 생각해보면 큐의 균형 여부는 당연히 큐의 길이(처음에는 괄호는 짝이 맞아야하니까 짝수, 홀수 이런 것도 떠올려보기도 했지만...)와는 관련이 없고, 가장 중요하게도 괄호 순서에 초점을 두어야한다.

 

예외가 있으면 안 되니까 다양한 입력 예시를 모두 생각하고 고려해보며 코드를 짜야함을 또 명심했다.

 

시도 2) (최종 코드) 스택을 이용하기

괄호 순서에 유의하며 스택을 이용한 코드로 바꿨다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class BOJ_4949_2 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String st = "";
        StringBuilder sb = new StringBuilder();

        while (true) {
            st = br.readLine();

            if (st.equals(".")) break;

            if (isBalanced(st))
                sb.append("yes\n");

            else sb.append("no\n");
        }
        System.out.println(sb);
    }

    public static boolean isBalanced(String st) {
        Stack<Character> stack = new Stack<>();

        for (char c : st.toCharArray()) {
            if (c == '(' || c == '[')
                stack.push(c);

            else if ((c == ')' || c == ']')) {
                if (stack.isEmpty())
                    return false;

                else {
                    char top = stack.pop();

                    if ((top == '(' && c != ')') || (top == '[' && c != ']'))
                        return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

 

생각보다 더욱 간단한 로직으로 풀 수 있는 문제였다.

 

추가적으로 달라진 점이 있다면, 앞선 코드에서는 문장의 모든 괄호 (,[,),], .을 덱(deque)에 다 넣고 나서 균형한지 판단했지만, 이번에는 순차적으로 스택에 ( 과 [ 만 넣으면서 동시에 균형한지 판단(짝이 맞으면 pop)한다는 것이다.

 

그리고 )이나 ] 이 나오면 스택 안의 top 요소- ( 또는 [ - 를 꺼내 비교하고, 짝이 맞지 않는다면 false를 반환해 no가 출력되게 하는 것이다. 괄호 검사 반복문을 마쳤을 때는 stack.isEmpty()의 결과를 반환해 스택이 모두 비었다면 true, 즉 균형 있는 스택, 스택에 아직 요소가 있다면 false, 불균형 스택이 된다.

 

---

문제를 봤을 때 pop, push가 있는 스택, 큐나 덱을 써야겠다고 생각은 했고, 모든 요소를 넣어야 판별이 될거라 처음에는 생각했다. 그래서 코드가 복잡해지고 count 변수도 생기고 했었다... 하지만 이 문제에서는 모든 괄호를 넣는 게 아니라 시작 괄호들만을 넣고 끝 괄호와 비교해서 스택에서 요소들을 pop 한다는 발상이 나에게는 새로웠다. 

 

그리고 다양한 예시, 예외 상황을 눈흐릿..하며 무시하지 말고 귀기울이자고 다짐했다. "여기선 이 논리가 당연하겠지~"라며 어물쩡 넘어 갔던 사소한 부분들로부터 예외 상황을 고려하지 못한 코드를 낳는다는 점을 명심하며... 

 

나의 부족한 점을 깨달을 수 있는 문제였다!