[백준] 9012번: 괄호 (JAVA)

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

문제 접근

이러면 안되지만 알고리즘 분류가 자료구조, 문자열, 스택으로 되어 있어서.. 스택을 사용하여서 풀면 되겠구나 라고 생각했습니다 ㅎㅎ;; 먼저 스택이란 데이터를 하나씩 쌓아 올린 형태의 자료 구조로, 가장 나중에 들어온 데이터가 가장 먼저 나가는 후입선출(Last In Fisrt Out)을 구조입니다. 스택의 활용 예시로는 웹 브라우저 뒤로 가기, 문서 작업에서 ctrl+z 등이 있습니다.

 

그래서 이 문제에서는 다음과 같이 스택을 적용했습니다:

1. 문자가 '(' 이면 스택에 넣는다.
2. 문자가 ')' 이면 스택이 비어있는지 검사한다.
3. 만약 비어있으면 ')'를 스택에 넣고 break를 사용하여 for문을 빠져 나간다 (스택이 비어있으면, '('가 없는 상태이므로, VPS를 만족할 수 없는 상태 -> 따라서 더이상 for문을 돌리는 것이 무의미하다.)
4. 비어있지 않으면 스택에 넣지 않고, 가장 위에 있는 데이터를 제거한다. 
5. for문이 끝나고 스택이 비어 있는지 검사: 비어 있지 않으면 NO 출력, 비어 있으면 YES 출력

전체 코드

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

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        for(int i = 0; i < n; i++) {
            String str = br.readLine();

            Stack<Character> stack = new Stack<Character>();

            for(int j = 0; j < str.length(); j++) {
                if(str.charAt(j) == '(') {
                    stack.push(str.charAt(j));
                } else {
                    //비어있는지를 확인
                    if(stack.empty()) {
                        stack.push(str.charAt(j));
                        break;
                    } else {
                        stack.pop();
                    }
                }
            }
            if(stack.empty()) bw.write("YES\n");
            else bw.write("NO\n");
        }
        bw.close();
    }
}

• push(): 데이터를 스택에 추가한다.
• pop(): 가장 위에 있는 데이터를 스택에서 제거한다.

push를 하면 그림과 같이 위에 가장 위에 쌓이며, pop을 하면 가장 위에 있는게 나가집니다!

 

읽어주셔서 감사합니다!