[BOJ/Java] 괄호 (9012)

괄호 (9012)

1. 문제 분석

문제 개요

• 여러 개의 괄호 문자열이 주어졌을 때, 각 문자열이 올바른 괄호로 구성되어 있는지 확인하는 문제이다.
• 괄호가 올바르게 구성되려면 여는 괄호 (와 닫는 괄호 )가 쌍을 이루어야 하며, 그 순서도 맞아야 한다.

입력 형식

• 첫 줄에 검사할 괄호 문자열의 개수 n이 주어진다.
• 다음 n줄에 각각 하나씩의 괄호 문자열이 주어진다.

출력 형식

• 각 문자열에 대해 올바른 괄호 구성이라면 "YES", 그렇지 않다면 "NO"를 출력한다.

2. 알고리즘 종류

이 문제는 스택을 이용한 괄호 유효성 검사 문제로, 여는 괄호는 스택에 넣고, 닫는 괄호가 나오면 스택에서 제거하는 방식으로 해결할 수 있다.

3. 주요 부분 및 코드 작성 방법

1. 스택 사용

• 여는 괄호 (는 스택에 추가하고, 닫는 괄호 )가 나오면 스택에서 여는 괄호를 하나 제거한다.
• 만약 닫는 괄호가 나왔을 때 스택이 비어있다면, 이는 잘못된 괄호 구성이다.

2. 유효성 체크

• 문자열을 모두 검사한 후에도 스택이 비어있지 않다면 여는 괄호가 더 많다는 의미이므로 잘못된 구성이다.

4. 코드 설명

메인 함수 (main)

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());  // 검사할 괄호 문자열의 개수를 입력받음

        for (int i = 0; i < n; i++) {
            String word = br.readLine().trim();  // 각 괄호 문자열을 입력받음
            Stack<Character> stack = new Stack<>();  // 괄호를 저장할 스택
            boolean isValid = true;  // 괄호의 유효성을 나타내는 변수

            for (char ch : word.toCharArray()) {
                if (ch == '(') {
                    stack.push(ch);  // 여는 괄호는 스택에 추가
                } else if (ch == ')') {
                    if (stack.isEmpty()) {
                        isValid = false;  // 스택이 비어있으면 잘못된 괄호
                        break;
                    } else {
                        stack.pop();  // 닫는 괄호가 나오면 스택에서 하나 제거
                    }
                }
            }

            // 스택이 비어있지 않으면 여는 괄호가 더 많다는 뜻
            if (!isValid || !stack.isEmpty()) {
                System.out.println("NO");
            } else {
                System.out.println("YES");
            }
        }
    }
}

• BufferedReader를 사용하여 입력을 처리하고, 괄호 문자열의 개수를 n으로 받아 각 문자열을 검사한다.
• 문자열을 순회하며 여는 괄호가 나오면 스택에 넣고, 닫는 괄호가 나오면 스택에서 제거한다.
• 스택이 비어있지 않거나 검사 도중 문제가 발생하면 "NO"를 출력하고, 모든 검사가 끝난 후에도 문제가 없으면 "YES"를 출력한다.

5. 전체 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());  // 검사할 괄호 문자열의 개수를 입력받음

        for (int i = 0; i < n; i++) {
            String word = br.readLine().trim();  // 각 괄호 문자열을 입력받음
            Stack<Character> stack = new Stack<>();  // 괄호를 저장할 스택
            boolean isValid = true;  // 괄호의 유효성을 나타내는 변수

            for (char ch : word.toCharArray()) {
                if (ch == '(') {
                    stack.push(ch);  // 여는 괄호는 스택에 추가
                } else if (ch == ')') {
                    if (stack.isEmpty()) {
                        isValid = false;  // 스택이 비어있으면 잘못된 괄호
                        break;
                    } else {
                        stack.pop();  // 닫는 괄호가 나오면 스택에서 하나 제거
                    }
                }
            }

            // 스택이 비어있지 않으면 여는 괄호가 더 많다는 뜻
            if (!isValid || !stack.isEmpty()) {
                System.out.println("NO");
            } else {
                System.out.println("YES");
            }
        }
    }
}