[백준] 23253번: 자료구조는 정말 최고야 - JAVA[랜덤 마라톤]

https://www.acmicpc.net/problem/23253

실버이상 난이도문제에서 오류 없이 한 번에 통과하는 건 굉장히 오랜만인 거 같다.

 

문제 분석을 조금 해보자면 이 문제가 Stack으로 풀수 있는지는 잘 모르겠지만 아무리 봐도 배열을 사용해서 문제를 

해결할 수 있겠다는 생각이 들어 짜봤는데 한번에 통과해서 좀 당황스러웠다.(그런데 솔직히 런타임 애러 날 거라고 생각했는데 통과돼서 심히 매우 당황)

---

◎알고리즘 [풀이과정]

내가 배열로 문제를 풀수 있겠다고 생각한 이유는 가장 아래에 있는 책과 그다음 책의 번호를 비교하여 아래 책의 번호가 작다면 책을 순서대로 나열할 수 없다고 생각했기 때문이다.

 

가장 나중에 들어간 값이 가장 먼저 나오는 LIFO의 형태를 가진 Stack의 구조상 아래에 자신보다 낮의 번호의 책이 있다면 결코 순서대로 책을 나열할수 없다.

 

 이 생각을 가지고 코딩을 하니 쉽게 문제를 해결할수 있었다.

import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();	//교과서 수
		int M = sc.nextInt();	//더미 수
		int count = 0;
		
		for(int i =0;i<M;i++) {
			int num = sc.nextInt();	//책 갯수
			int[] order = new int[num];
			for(int j = 0;j<num;j++) {
				order[j] = sc.nextInt();
			}
			
			for(int j = 0;j<num-1;j++) {
				if(order[j]<order[j+1] && count != 1) {
					count = 1;
				}
				else continue;
			}
		}
		
		if(count == 1) {
			System.out.println("No");
		}
		else System.out.println("Yes");
	}
}