[Baekjoon 9012번] 괄호 풀이 (with 스택)

문제 9012번 - 괄호

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

9012번: 괄호

 

 

 

풀이

package seohae.algorithm.level1;

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;
import java.util.Stack;

/**
 * 괄호
 * https://www.acmicpc.net/problem/9012
 */
public class Problem_004_9012 {
    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);

        int num = in.nextInt();

        for(int i = 0; i < num; i++) {
            /* 입력을 할때마다 함수 호출 */
            System.out.println(solution(in.next()));
        }
    }

    public static String solution(String s) {
        String result = "NO";

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

        for (int i = 0; i < s.length(); i++) {
            /* '(' 일때 stack push */
            if (s.charAt(i) == '(') {
                stack.push(s.charAt(i));
            } else if (s.charAt(i) == ')') {
                /* ')' 일때 stack 에서 짝 '(' 을 꺼낸다 */
                if (!stack.isEmpty()) { /* 비어져있지 않을때 */
                    stack.pop(); /* '(' 1개 pop */
                    result = "YES";
                } else { /* stack 이 비어져있다면 닫히지 않는다는 의미 */
                    result = "NO";
                    break;
                }
            }
        }

        /* stack 이 비어져있지 않다면 '('가 남아있다는 의미 */
        if (!stack.isEmpty()) {
            result = "NO";
        }

        return result;
    }
}

 

괄호의 짝은 () 이다. Stack 에 '(' 은 push 하고, ')'일때에는 stack 에 짝을 맺을 수 있는 '(' 를 pop() 해올 수 있는지 확인을 하면 된다. 그리고 마지막엔 Stack 이 비어져있는지 확인을 해야한다. 만약 비어져있지 않다면 ')' 와 짝을 이루지 못한 '('가 남아있다는 의미로, "NO"를 리턴해야한다.