[BaekJoon] #4949 균형잡힌 세상

문제분석

앞에서 풀었던 괄호문제를 변형하면 됩니다.

입력

각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다.

입력의 종료조건으로 맨 마지막에 온점 하나(".")가 들어온다.

출력

각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.

문제접근

이전 괄호문제처럼 Stack을 이용해서 문제를 풀었습니다.
앞의 문제와 비슷하지만 다른 조건들이 추가되었습니다.
이전 괄호문제는 입력으로 한가지 종류의 괄호만 들어왔고, 그 괄호가 pair를 이루는지 확인하는 문제였지만, 이 문제에서는 두가지 종류의 괄호와 여러 알파벳이 섞인 입력에서 괄호의 짝이 맞는지 확인해야합니다.

이전 #9012 괄호 문제의 문제를 해결하는 부분의 알고리즘은 다음과 같습니다.

public static String solve(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);

            if (ch == '(') {
                stack.push(ch);
            } else if (stack.isEmpty()) {
                return "NO";
            } else {
                stack.pop();
            }
        }

        if (stack.isEmpty()) {
            return "YES";
        } else {
            return "NO";
        }
    }

위의 코드를 변형하여 아래와 같이 작성해주었습니다.

public static String solve(String s) {

        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(' || ch == '[') {
                stack.push(ch);
            } else if (ch == ')') {
                // 비어있거나, 본인 짝이 스택에 존재하지 않으면 no
                if (stack.isEmpty() || stack.peek() != '(') {
                    return "no";
                } else {
                    stack.pop();
                }
            } else if (ch ==']'){
                if (stack.isEmpty() || stack.peek() != '[') {
                    return "no";
                } else {
                    stack.pop();
                }
            }

            }
        if (stack.isEmpty()) {
            return "yes";
        } else {
            return "no";
        }

    }

첫 조건문에서는 여는 괄호 '(' 혹은 '[' 가 들어오면 Stack에 push합니다.

그 이후, 여는 괄호가 아닌 경우에 한해서 입력으로 ']' 혹은 ')'가 들어오는 케이스 두개로 나누어 조건식을 작성해주었습니다.

• ')' 가 입력으로 들어왔을때, 만약 스택이 비어있다면 해당 닫는 괄호의 pair이 존재하지 않다는것을 의미하므로 no를 리턴합니다.
• 그러나, 괄호의 종류가 두가지이기 때문에, ')' 가 입력으로 들어왔을때 '[' 가 스택에 존재할 가능성도 있습니다.
• 위와 같은 경우, 스택이 비어있지 않아 pair가 존재할 수 있는 것 처럼 보일 수 있으나 입력괄호의 pair가 아니기 때문에 입력괄호의 pair는 존재하지 않습니다.
  그렇기 때문에, 해당 입력괄호의 짝에 해당하는지 구분해주어야 합니다.

위의 조건들을 지나친 다음에는 본인의 pair가 존재한다는것을 의미하기 때문에, pop해줍니다.

괄호가 두가지 종류이므로, ')' 인경우와 '}' 인 경우를 나누어서 조건문을 작성해주었습니다.

이후, 최종적으로 스택을 점검한 이후 코드가 마무리됩니다.

다른 조건들에 대한 설명은 아래와 같습니다.

• 입출력을 위해 BufferedReader와 StringBuilder를 사용하였습니다.

• main에 입력종료조건을 위해, while문을 이용해 계속해서 입력을 받다가 '.' 이 들어오면 break 하는 조건식을 추가해주었습니다.

• solve함수에서 입력받은 문자열의 길이만큼 for문을 반복하여 모든 문자열을 순회하여 조건에 맞는 리턴값을 도출해 냅니다.

• charAt을 이용하여 문자열을 인덱스별로 접근해주었습니다.

code

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

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

        while (true) {
            s = br.readLine();
            if (s.equals(".")) {break;}

        sb.append(solve(s)).append("\n");
        }
        System.out.println(sb);
    }

    public static String solve(String s) {

        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(' || ch == '[') {
                stack.push(ch);
            } else if (ch == ')') {
                // 비어있거나, 본인 짝이 스택에 존재하지 않으면 no
                if (stack.isEmpty() || stack.peek() != '(') {
                    return "no";
                } else {
                    stack.pop();
                }
            } else if (ch ==']'){
                if (stack.isEmpty() || stack.peek() != '[') {
                    return "no";
                } else {
                    stack.pop();
                }
            }

            }
        if (stack.isEmpty()) {
            return "yes";
        } else {
            return "no";
        }

    }
}

출력결과