짝이 맞지 않는 괄호

풀이

매우 직관적으로 스택을 써야 한다는 것을 알 수 있습니다. 약간 생각해야할 것은 예외 처리입니다. 스택이 비어있거나 모든 식을 다 검사하고 여는 괄호가 스택에 남아있는 경우를 처리해줘야 합니다.

구현

import java.util.*;

public class Main {

    public static String str;
    public static boolean result;

    public static void input(Scanner scanner) {
        str = scanner.next();
    }

    public static void solve() {
        result = wellMatched(str);
    }

    public static boolean wellMatched(String str) {
        // 여는 괄호 문자들과 닫는 괄호 문자들
        final String opening = "({[", closing = ")}]";
        // 이미 열린 괄호들을 순서대로 담는 스택
        Stack<Character> openStack = new Stack<>();
        for (int i = 0; i < str.length(); i++) {
            // 여는 괄호인지 닫는 괄호인지 확인한다.
            if (opening.indexOf(str.charAt(i)) != -1) {
                // 여는 괄호라면 무조건 스택에 집어넣는다.
                openStack.push(str.charAt(i));
            } else {
                // 이 외의 경우 스택 맨 위의 문자와 맞춰보자.
                // 스택이 비어 있는 경우에는 실패
                if (openStack.empty()) return false;
                // 서로 짝이 맞지 않아도 실패
                if (opening.indexOf(openStack.peek()) != closing.indexOf(str.charAt(i)))
                    return false;
                // 짝을 맞춘 괄호는 스택에서 뺀다.
                openStack.pop();
            }
        }
        // 닫히지 않은 괄호가 없어야 성공
        return openStack.empty();
    }

    public static void output() {
        if (result)
            System.out.println("YES");
        else
            System.out.println("NO");
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testCase = scanner.nextInt();
        for (int i = 0; i < testCase; i++) {
            input(scanner);
            solve();
            output();
        }
    }
}

회고