[SWEA] 코드 편집기 괄호 짝 검사 (Java)

1. 문제 요약

한 줄의 코드에서 소괄호 ()와 중괄호 {}의 짝이 올바른지 판정한다. 올바르면 1, 아니면 0.

• 여는 괄호는 짝이 되는 닫는 괄호와 만나야 하고, 서로 엇갈리면 안 된다 ({( )}는 O, {( })는 X)
• 따옴표(', ")로 감싼 구간은 문자열이므로 그 안의 괄호는 전부 무시한다
• T ≤ 50

2. 접근 과정

괄호 짝 맞추기는 스택

가장 최근에 열린 괄호가 가장 먼저 닫혀야 한다.

• 여는 괄호 → push
• 닫는 괄호 → pop 해서 짝이 맞는지 확인
• 다 읽고 스택이 비어 있으면 성공

따옴표를 어떻게 다룰 것인가

boolean + char 두 개로 나눌 수도 있지만, char 하나에 "닫힘(0)"과 "종류"를 같이 담으면 관리할 상태가 하나로 된다.

3. 코드

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

public class Solution {

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

        int T = Integer.parseInt(br.readLine().trim());

        for (int tc = 1; tc <= T; tc++) {
            String line = br.readLine();
            sb.append('#').append(tc).append(' ')
              .append(isValid(line) ? 1 : 0).append('\n');
        }

        System.out.print(sb);
    }

    static boolean isValid(String line) {
        char[] stack = new char[line.length()];
        int top = 0;
        char quote = 0;   

        for (int i = 0; i < line.length(); i++) {
            char c = line.charAt(i);

            if (quote != 0) {                  
                if (c == quote) quote = 0;
                continue;                     
            }

            if (c == '\'' || c == '"') {      
                quote = c;
            } else if (c == '(' || c == '{') {
                stack[top++] = c;
            } else if (c == ')') {
                if (top == 0 || stack[--top] != '(') return false;
            } else if (c == '}') {
                if (top == 0 || stack[--top] != '{') return false;
            }
        }

        return top == 0;                    
    }
}

시간복잡도: O(L)
공간복잡도: O(L)

Stack 대신 배열

자바의 java.util.Stack은 Vector를 상속해 모든 메서드가 synchronized라 단일 스레드에서는 불필요한 오버헤드가 있다. 대안으로 ArrayDeque가 권장되지만, 이 문제처럼 최대 크기를 미리 알 수 있으면 char[] + int top이 가장 빠르고 박싱도 없다.

면접에서 "왜 Stack을 안 쓰냐"는 질문이 나오면 위 이유를 답할 수 있어야겠다.