[알고리즘][백준][JAVA] 9012번 : 괄호

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

9012번: 괄호

스택을 이용하는 대표적인 문제이다.

세 가지 경우로 나누어 생각할 수 있는데,

1. 올바르게 괄호가 구성된 경우 ( 모든 과정이 끝나고 난 후 최종 스택이 empty 인 경우)

2. 모든 과정이 끝났는데, 스택에 남은 원소가 있는 경우

3. 닫는 괄호가 스택에 들어왔는데, pop 할 원소가 없는 경우

로 나누어 코드를 짜면 된다.

 

import java.util.*;

public class Main {
    public static void main(String[] args){
        int N;
        Scanner sc = new Scanner(System.in);
        N= sc.nextInt();

        for (int i=0;i<N;i++){
            System.out.println(par(sc.next()));
        }
    }

    public static String par(String a){
        Stack<Character> stack = new Stack<>();

        for (int i=0;i<a.length();i++){         //character의 개수만큼 for문 돌리기
            char c = a.charAt(i);

            if (c=='(')
                stack.push(c);              // "(" 이면, 스택에 넣는다.
            else if (stack.empty())
                return "NO";                // ")"를 입력받았지만, pop할 원소가 없을 경우 return NO (3번경우)
            else
                stack.pop();                // ")"를 입력받으면, pop
        }

        if (stack.empty())
            return "YES";                   // 모든 과정이 끝났는데 empty이면 성공이므로 return YES (1번경우)
        else
            return "NO";                    // 모든 과정이 끝났는데 원소가 남아있으면 실패이므로 return NO (2번경우)
    }
}