[코딩테스트] SWEA 1218 괄호 짝짓기(Java)

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
SWEA 1218 괄호 짝짓기입니다.

포인트

닫힌 괄호 ), ], }, >는 항상 그에 대응하는 열린 괄호 (, [, {, <보다 뒤에 나와야 합니다.
따라서 문자열을 순회하면서 닫힌 괄호를 만날 때마다 최근에 열린 괄호와 짝이 맞는지 확인해주는 방식으로 유효성을 판단할 수 있습니다.

 

이를 위해 가장 적절한 자료구조는 LIFO(Last-In-First-Out) 구조인 스택(Stack) 입니다.

• 열린 괄호는 스택에 저장하고,
• 닫힌 괄호를 만났을 때 스택의 top과 매칭되는 열린 괄호인지 확인합니다.
• 괄호가 올바르게 짝지어지지 않았거나, 스택이 비어있는 경우 → 올바르지 않은 문자열로 판단합니다.
• (), {}, [], <>의 네 종류 괄호 짝을 모두 고려합니다.

소스코드

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

public class Q1218 {
    private static int tc = 10, len;
    private static Set<Character> openSet = new HashSet<>();
    private static Map<Character, Character> closeMap = new HashMap<>();

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

        for (int t = 1; t <= tc; t++) {
            sb.append("#").append(t).append(" ");
            len = Integer.parseInt(br.readLine());
            Stack<Character> validation = new Stack<>();
            String line = br.readLine();
            boolean check = true;
            for (int i = 0; i < len; i++) {
                char cur = line.charAt(i);
                if (openSet.contains(cur)) {
                    validation.add(cur);
                } else {
                    char open = closeMap.get(cur);
                    if (open == validation.peek()) {
                        validation.pop();
                    } else {
                        check = false;
                        break;
                    }
                }
            }
            if (!validation.isEmpty()) {
                check = false;
            }
            sb.append(check ? 1 : 0).append("\n");
        }
        System.out.println(sb);
    }

    private static void init() {
        openSet.add('(');
        openSet.add('{');
        openSet.add('[');
        openSet.add('<');

        closeMap.put(')', '(');
        closeMap.put('}', '{');
        closeMap.put(']', '[');
        closeMap.put('>', '<');
    }
}

코드 설명

• 전역변수
  • openSet: 여는 괄호 집합
  • closeMap: 닫는 괄호 -> 여는 괄호 대응 매핑
• init() 함수
  
  • 열린 괄호들을 Set에 넣고, 닫힌 괄호의 대응 관계를 Map에 저장합니다.
  • 코드의 유연성과 가독성을 높이기 위해 사용된 초기 설정입니다.

main() 함수

Stack<Character> validation = new Stack<>();
boolean check = true;

• 스택을 이용한 검사
  • validation 스택을 사용해 열린 괄호를 저장합니다.
  • check 변수는 문자열의 유효성을 판별하는 플래그입니다.

for (int i = 0; i < len; i++) {
    char cur = line.charAt(i);
    if (openSet.contains(cur)) {
        validation.add(cur);
    } else {
        char open = closeMap.get(cur);
        if (open == validation.peek()) {
            validation.pop();
        } else {
            check = false;
            break;
        }
    }
}

• 문자 순회 및 처리
  • 열린 괄호 → 스택에 push
  • 닫힌 괄호 → 스택 top과 비교 후 pop 또는 실패 처리
  • 만약 스택이 비어있거나 짝이 맞지 않으면 실패로 처리
• 반복이 끝났는데도 스택이 비어있지 않으면, 열린 괄호가 닫히지 않은 경우 -> 실패