백준 17074번: 정렬

백준 17074번: : 정렬

 

배열에 저장된 수를 하나씩 제외해서 배열 전체가 정렬이 되는지 확인하면 시간제한을 초과합니다.

경우의 수를 나눠

i) 이미 정렬이 되어 있는 경우

- 이미 배열이 정렬 되어 있으므로 어느 수를 버리더라도 정렬이 유지되므로 N개의 경우의 수가 나옵니다.

ii) 한 구간 빼고 정렬이 되어 있는 경우

- array[i-1] <= array[i+1] (i번째 배열의 방이 정렬되지 않은 수) 인 경우 i번째 배열의 방을 제거하면 전제 배열이 정렬됩니다.

-array[i] <= array[i+2] (i번째 배열의 방이 정렬되지 않은 수) 인 경우 i+1번째 배열의 방을 제거하면 전체 배열이 정렬됩니다.

->위의 두 가지 조건을 모두 만족하면 경우의 수는 2, 한 가지만 만족하면 경우의 수는 1, 모두 만족하지 못하면 경우의 수는 0을 출력하면 됩니다.

iii) 두 구간 이상 정렬이 되어 있지 않은 경우

- 어느 수를 버리더라도 정렬이 되지 않으므로 0개의 경우의 수가 나옵니다.

 

	import java.util.Scanner;
	public class Main {
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int decline = 0;
	int tmp = 0;
	int c = 0;
	int n = sc.nextInt();
	int[] a = new int[n];
	for(int i = 0; i < n; i++){
	a[i] = sc.nextInt();
	}
	for(int i = 0; i < n-1; i++) {
	if (a[i] > a[i + 1]) {
	tmp = i;
	decline++;
	}
	}
	switch (decline){
	case 0:
	System.out.println(n);
	break;
	case 1:
	if(tmp == n-2){
	if(a[tmp-1] <= a[tmp+1])
	System.out.println("2");
	else
	System.out.println("1");
	}
	else if(tmp == 0){
	if(a[tmp] <= a[tmp+2])
	System.out.println("2");
	else
	System.out.println("1");
	}
	else{
	if(a[tmp-1] <= a[tmp+1])
	c++;
	if(a[tmp] <= a[tmp+2])
	c++;
	System.out.println(c);
	}
	break;
	default:
	System.out.println("0");
	break;
	}
	sc.close();
	}
	}

view raw BOJ_17074.java hosted with ❤ by GitHub