[Javaアルゴリズム]5-1.右かっこ(Stack,Queue)

🌵 Stack ?

積み重ねとは「積み重ね」という意味で、データを一つ一つ積み重ねていく形の資料構造です.

上図に示すように、データは順番に積み上げられ、最後に挿入されたデータが最初に削除される構成となっている.
また、スタックは指定された方向にのみスタックでき、上部の指定された位置からのみアクセスできます.
新しく挿入した資料はtopが指す一番上に積み上げられ、資料を削除するときもtopで削除できます.
挿入演算はpush、削除演算はpopで行うことができる.
このスタックの構造を후입 선출の構造と呼ぶ.
略称LIFO(Last In First Out).

🥦 Queue?

キューはスタックとは異なり、先入先出の「先入先出」構造とFIFO構造を有する.

削除演算を実行する場所はフロントエンド(front)、挿入演算する場所は後置(hut)、FIFO構造のためスタックと異なりキューの一端は挿入操作、他端は削除操作である.
キューが後置で実行される挿入演算を인큐(Enqueue)、フロントエンドで実行される削除演算を디큐(Dequeue)と呼ぶ.

🌼 Problem

🍔 Solution 1

import java.util.Scanner;
import java.util.Stack;

public class Main {

    public static String Solution(String input){
        String answer = "YES";
        Stack<Character> st = new Stack<>();

        for(char ch : input.toCharArray()){
            if(ch=='('){
                st.push('(');
            }else if(!st.isEmpty()){
                st.pop();
            }else if(st.isEmpty()){
                answer = "NO";
            }
        }

        if(!st.isEmpty()){
            answer = "NO";
        }
        return answer;
    }


    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        String input = in.next();
        System.out.println(Solution(input));
    }
}

🍪 講師ソリューション-答えは多くありません!

import java.util.Scanner;
import java.util.Stack;

public class Main {

    // 강사
    public static String Solution(String str){
        String answer = "YES";
        Stack<Character> stack = new Stack<>();

        for(char x : str.toCharArray()){
            if(x=='('){
                stack.push(x);
            }else{
                // 닫는 괄호 ')'가 많은 경우, stack.pop으로 인해 stack이 비어있을 수 있다.
                if(stack.isEmpty()) return "NO";
                stack.pop();
            }
        }
        // 여는 괄호 '('가 많은 경우, stack.pop이 모두 이뤄지지 못하여 stack이 비어있지 않음
        if(!stack.isEmpty()){
            return "NO";
        }

        return answer;
    }


    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        String input = in.next();
        System.out.println(Solution(input));
    }
}

🍖Issue🍖

if(stack.isEmpty()) return "NO";

この部分をanswer= "NO";と書くとruntime errorが発生します.
)で始まる文字列かもしれません.answer = "NO"コードの後、stack.pop()を実行できないと判断して発生した問題に接する.
ソース:https://jud00.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9DStack%EA%B3%BC-%ED%81%90Queue%EC%97%90-%EB%8C%80%ED%95%B4%EC%84%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EC%9E%90