백준(BOJ) 4949 : 균형잡힌 세상 (실버4) / 자바(Java) 풀이

문제

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

3줄 요약

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

코드

// package boj4949;

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));

        while (true) {
            // 한 줄의 문자열을 입력받음
            String s = br.readLine();
            // 입력이 "."이면 반복을 종료
            if (s.equals(".")) {
                break;
            }
            // 괄호 검사를 위한 스택 생성
            Stack<Character> stack = new Stack<>();
            // 초기 답변을 "yes"로 설정
            String answer = "yes";

            // 문자열을 한 글자씩 순회
            for (char v : s.toCharArray()) {
                switch (v) {
                    case ')':
                        // 닫는 소괄호를 만났을 때
                        if (stack.isEmpty() || stack.peek() != '(') {
                            answer = "no";
                            break;
                        } else {
                            stack.pop();
                        }
                        break;
                    case ']':
                        // 닫는 대괄호를 만났을 때
                        if (stack.isEmpty() || stack.peek() != '[') {
                            answer = "no";
                            break;
                        } else {
                            stack.pop();
                        }
                        break;
                    case '(':
                        // 여는 소괄호를 스택에 푸쉬
                        stack.push(v);
                        break;
                    case '[':
                        // 여는 대괄호를 스택에 푸쉬
                        stack.push(v);
                        break;
                }
                // "no"가 결정되면 반복 종료
                if (answer.equals("no")) {
                    break;
                }
            }
            // 모든 괄호를 처리한 후에도 스택이 비어있지 않으면 "no"로 설정
            if (!stack.isEmpty()) {
                answer = "no";
            }
            // 결과를 출력 버퍼에 저장
            bw.write(answer);
            bw.newLine();
        }
        // 출력 버퍼를 실제 출력
        bw.flush();
        // 리소스 해제
        br.close();
        bw.close();
    }
}