[Algorithm] 올바른 괄호 (Java) - Stack 보단 Deque

설명

괄호가 입력되면 올바른 괄호이면 “YES", 올바르지 않으면 ”NO"를 출력합니다.

(())() 이것은 괄호의 쌍이 올바르게 위치하는 거지만, (()()))은 올바른 괄호가 아니다.

입력

첫 번째 줄에 괄호 문자열이 입력됩니다. 문자열의 최대 길이는 30이다.

출력

첫 번째 줄에 YES, NO를 출력한다.

예시 입력 1 

(()(()))(()

예시 출력 1

NO

---

Stack 자료구조를 이용하는 문제는 맞지만, 현재 Stack 클래스는 사용하지 않는다고 배웠다.

스택은 자바 1버전에서 사용하던 Vector 를 상속받은 클래스라는데.. 이제는 하위 버전 호환용으로만 존재할 뿐 사용하지 않기 때문에 Deque 로 풀었다.

Deque는 스택의 push(), pop() 메서드와 Queue의 offer(), poll() 메서드 모두 지원하기 때문에 아주 효율적인 자료구조이다.

import java.util.*;

//반드시 여는 괄호가 있어야함을 인지하고 풀자
public class GualHo {

    public static void main(String[] args) {

        Deque<Character> deque = new ArrayDeque<>();

        Scanner sc = new Scanner(System.in);
        String str = sc.next();

        solution(str, deque);

    }
    
    
// 닫는 괄호는 굳이 push 할 필요가 없다
    private static void solution(String str, Deque<Character> deque) {
        char[] charArray = str.toCharArray();

        for (char c : charArray) {
            if (c == '(') {
                deque.push('(');
            } else if (c == ')') {
                if (deque.isEmpty()) {
                    System.out.println("NO");
                    return;
                }
                deque.pop();
            }
        }

        if (deque.isEmpty()) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}