[백준] 23253번 - 자료구조는 정말 최고야 (Silver 5)

문제 링크

[백준] 23253번 - 자료구조는 정말 최고야 (Silver 5)

문제 설명

N권의 교과서 1~N이 M개의 더미로 아무렇게나 쌓여있다.
각 더미의 맨 위에서만 교과서를 꺼낼 수 있을 때, 교과서를 번호 순으로 꺼낼 수 있는지를 출력한다.

정답 코드 및 설명

각 더미가 맨 아래부터 내림차순으로 정렬되어있다면 교과서를 번호 순으로 꺼낼 수 있다.
더미의 맨 위에 있는 책 중 번호가 가장 작은 것부터 꺼내는 것을 반복하면 되기 때문이다.
반대로, 각 더미가 내림차순으로 정렬되어 있지 않으면 정렬되지 않은 순으로 꺼내야만 하는 구간이 존재한다.
예를 들어 교과서 5가 교과서 3보다 위에 있다면, 어떻게 꺼내든 교과서 3을 교과서 5보다 늦게 꺼내게 된다.
따라서 각 더미가 내림차순으로 정렬되어 있는지의 여부만 체크하여 결과를 출력하면 된다.

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class BOJ23253 {
    int n, m;
    ArrayList<Integer>[] index;

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        index = new ArrayList[m];
        for (int i = 0; i < m; i++) {
            index[i] = new ArrayList<>();
            br.readLine();
            st = new StringTokenizer(br.readLine());
            while (st.hasMoreTokens()) {
                index[i].add(Integer.parseInt(st.nextToken()));
            }
        }
    }

    boolean isAble() {
        for (int i = 0; i < m; i++) {
            for (int j = 1; j < index[i].size(); j++) {
                if (index[i].get(j - 1) < index[i].get(j)) return false;
            }
        }
        return true;
    }

    void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        if (isAble()) bw.write("Yes");
        else bw.write("No");
        bw.close();
    }

    void solution() throws IOException {
        input();
        print();
    }

    public static void main(String[] args) throws IOException {
        new BOJ23253().solution();
    }
}