문제 내용은 입력으로 책 전체 권수와, 무더기의 갯수를 받은 뒤, 스택 형태로 책을 배치하고 1번부터 차례대로 뽑는다고 했을 때 순서대로 뽑을 수 있다면 Yes, 불가능하다면 No를 출력해주면 되는데, 문제 풀기 전 주의할 점은 제한 부분에서 숫자를 꼭 확인해주자
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] target = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
boolean ans = true;
for (int i = 0; i < target[1]; i++) {
br.readLine();
int[] books = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
for (int j = 0; j < books.length - 1; j++) {
if (books[j] < books[j + 1]) {
ans = false;
break;
}
}
}
System.out.println(ans ? "Yes" : "No");
}
}처음에 제한 숫자 별로 신경 안쓰고 for문 돌리면서, 숫자 스택별로 숫자 찾아주다가, 스택 갯수가 늘어날수록 소요시간이 지나치게 늘어나는 문제가 발생했는데
시간 제한에 걸리지 않고 풀어주려면, 스택을 만들 필요 없이 책 무더기별로 내림차순으로 잘 정렬되어 있으면 스택 돌리면서 문제가 발생할 수 없기에 정렬 여부만 확인한 뒤 문제가 없으면 Yes, 있으면 No를 출력해주면 끝이다
Leave a Reply