백준 23253 java : Stack 연습

첫 풀이는 문제가 요구하는 대로 스택 자료구조를 사용해 보았다.

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

public class bj23253 {

    static Scanner scanner = new Scanner(System.in);
    static int N, M;
    static Vector<Stack<Integer>> book = new Vector<>();


    public static void main(String[] args) {
        inputData();
        System.out.println(findAnswer());

        scanner.close();
    }

    public static void inputData(){
        //System.out.println("inputData()");
        int i, j, k, bookNum;

        N = scanner.nextInt();
        M = scanner.nextInt();
        for(i = 0; i < M; i++){
            k = scanner.nextInt();
            Stack <Integer> bookStack = new Stack<>();
            for(j = 0; j < k; j++){
                bookNum = scanner.nextInt();
                bookStack.push(bookNum);
            }
            book.add(bookStack);
        }
    }

    public static String findAnswer(){
        System.out.println("findAnswer()");
        boolean answer = true;
        int i, j, count = 1;

        while(true){
            for(i = 0; i < book.size(); i++){
                if(book.get(i).isEmpty())
                {
                    continue;
                }
                else if(book.get(i).peek() == count){
                    count++;
                    answer = true;
                    //System.out.println(book.get(i).pop());
                    System.out.println(i + "번째 더미의 " + book.get(i).peek() + "번 책 꺼내기");
                    book.get(i).pop();
                    break;
                }
                else{
                    answer = false;
                    continue;
                }
            }
            if(!answer){
                System.out.println("모든 책을 꺼내기 전 종료");
                answer = false;
                break;
            }
            if(count == N + 1){
                System.out.println("모든 책을 꺼냄");
                answer = true;
                break;
            }
        }

        if(answer)
        {
            return "Yes";
        }
        else{
            return "No";
        }
    }
}

그러나 시간 초과가 발생한다.
다른 풀이를 참고하던 중, 내가 구현한 방법은 문제가 요구하는 풀이는 맞지만, 모든 스택의 가장 위 요소를 모두 비교하다 보니 시간이 많이 소모된다.
모든 스택이 순서대로 제거되려면 각 스택이 전부 내림차순으로 정렬되어 있어야 한다. 기존 자료구조를 유지한채로 풀이만 수정해 보겠다.

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

public class bj23253 {

    static Scanner scanner = new Scanner(System.in);
    static int N, M;
    static Vector<Stack<Integer>> book = new Vector<>();


    public static void main(String[] args) {
        inputData();
        System.out.println(findAnswer());

        scanner.close();
    }

    public static void inputData(){
        System.out.println("inputData()");
        int i, j, k, bookNum;

        N = scanner.nextInt();
        M = scanner.nextInt();
        for(i = 0; i < M; i++){
            k = scanner.nextInt();
            Stack <Integer> bookStack = new Stack<>();
            for(j = 0; j < k; j++){
                bookNum = scanner.nextInt();
                bookStack.push(bookNum);
            }
            book.add(bookStack);
        }
    }

    public static String findAnswer(){
        System.out.println("findAnswer()");
        boolean answer = true;
        int i, j, count = 1;

//        while(true){
//            for(i = 0; i < book.size(); i++){
//                if(book.get(i).isEmpty())
//                {
//                    continue;
//                }
//                else if(book.get(i).peek() == count){
//                    count++;
//                    answer = true;
//                    System.out.println(book.get(i).pop());
//                    System.out.println(i + "번째 더미의 " + book.get(i).peek() + "번 책 꺼내기");
//                    book.get(i).pop();
//                    break;
//                }
//                else{
//                    answer = false;
//                    continue;
//                }
//            }
//            if(!answer){
//                System.out.println("모든 책을 꺼내기 전 종료");
//                answer = false;
//                break;
//            }
//            if(count == N + 1){
//                System.out.println("모든 책을 꺼냄");
//                answer = true;
//                break;
//            }
//        }
//
//        if(answer)
//        {
//            //return "Yes";
//        }
//        else{
//            //return "No";
//        }
        //->시간 초과

        //각 스택이 내림차순으로 정렬되어 있는지를 판단하면 다른 조건을 생각할 필요가 없다.
        for(i = 0; i < book.size(); i++){
            count = 0;
            System.out.println("\n" + i + "번째 책 무더기");
            while(!book.get(i).isEmpty()){
                if(book.get(i).peek() > count){
                    System.out.println(book.get(i).peek() + "번 책 꺼내기");
                    count = book.get(i).pop();
                }
                else{
                    return "No";
                }
            }
        }

        return "Yes";
    }
}