백준(BOJ) 9012 : 괄호 (실버4) / 자바(Java) 풀이

문제

https://www.acmicpc.net/problem/9012

3줄 요약

1. 스택 사용 이유: 스택은 괄호의 중첩 구조를 관리하기에 적합한 자료구조로, 여는 괄호를 스택에 쌓고 닫는 괄호는 스택에서 제거하여 짝을 맞춥니다. 이렇게 하면 괄호의 순서를 쉽게 관리할 수 있습니다.
2. 속도 측면: 스택을 사용하면 각 연산(삽입 및 삭제)이 O(1) 시간에 이루어지므로 전체 알고리즘의 시간 복잡도는 O(n)입니다. 이는 괄호 문자열의 길이에 비례하여 효율적으로 처리할 수 있음을 의미합니다.
3. 유효성 검사: 모든 괄호 문자열을 순회하며 스택을 이용해 짝을 맞추고, 닫는 괄호를 처리할 때 스택이 비어있으면 "NO"를 출력하며, 모든 처리가 끝난 후에도 스택이 비어있지 않으면 "NO"를 출력합니다. 모든 테스트 케이스에 대해 유효성을 검사하여 "YES" 또는 "NO"를 출력합니다.

코드

// package boj9012;

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        // 표준 입력을 파일로부터 읽도록 설정
        // System.setIn(new FileInputStream("src/input.txt"));

        // 표준 입력을 통해 데이터를 읽어옴
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 표준 출력을 통해 데이터를 출력함
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 테스트 케이스의 수를 입력받음
        int T = Integer.parseInt(br.readLine());
        // System.out.println(T);

        // 테스트 케이스 수만큼 반복
        for (int i = 0; i < T; i++) {
            // 괄호 문자열을 입력받음
            String s = br.readLine();
            // 괄호 검사를 위한 스택 생성
            Stack<String> stack = new Stack<>();
            // 초기 답변을 "YES"로 설정
            String answer = "YES";

            // 문자열을 한 글자씩 순회
            for (String v : s.split("")) {
                // 만약 닫는 괄호를 만났을 때
                if (v.equals(")")) {
                    // 스택이 비어있으면 잘못된 괄호열이므로 "NO"로 설정하고 반복 종료
                    if (stack.isEmpty()) {
                        answer = "NO";
                        break;
                    } else {
                        // 스택이 비어있지 않으면 열린 괄호 하나를 팝함
                        stack.pop();
                    }
                } else {
                    // 열린 괄호를 스택에 푸쉬
                    stack.push("(");
                }
            }

            // 모든 괄호를 처리한 후에도 스택이 비어있지 않으면 "NO"로 설정
            if (!stack.isEmpty()) {
                answer = "NO";
            }

            // 결과를 출력 버퍼에 저장
            bw.write(answer);
            bw.newLine();
        }

        // 출력 버퍼를 실제 출력
        bw.flush();
        // 리소스 해제
        br.close();
        bw.close();
    }

}