[백준BOJ] 17074번 정렬.java

 

백준 저지에서 팰린드롬수를 파이썬을 통해 풀어 보았다. 

 

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

17074번: 정렬

17074번 정렬.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

 

17074번 정렬

문제

정렬이란, 배열의 모든 원소가 비내림차순이 되도록 순서를 바꾸는 것을 말한다. 예를 들어 배열 [2, 1, 2, 3, 1]을 정렬하면 [1, 1, 2, 2, 3]이 된다.
남규는 정수 N개로 이루어진 배열 하나를 갖고 있다. 이 배열에서, 남규는 맘에 들지 않는 수를 정확히 하나 골라서 버릴 것이다.
예를 들어, 남규가 가진 배열이 [1, 2, 3, 2]라면, 남규는 1을 버려 [2, 3, 2]를 만들거나, 첫 2를 버려 [1, 3, 2]를 만들거나, 3을 버려 [1, 2, 2]를 만들거나, 두 번째 2를 버려 [1, 2, 3]을 만들 수 있다. 그리고 네 가지 경우 중 결과가 정렬된 것은 [1, 2, 2]와 [1, 2, 3] 두 가지이다. 남규는 이처럼, 수 하나를 버린 뒤 결과 배열이 정렬되어 있기를 원한다.
남규가 갖고 있는 배열이 주어지면, 수 하나를 버려 정렬된 배열을 남기는 방법의 수를 구해보도록 하자.

설명

하나씩 빼가면 이중 반복문으로 풀게되면 시간초과를 피할 수 없다. 반복문을 한 번만 써서 해결할 수 있는 아이디어가 필요하다.

 

만약 처음 배열 상태가 정렬되어 있다면 어떤 수를 빼더라도 정렬이 되어 있기 때문에 이 때 정답은 N이다.

 

처음 상태에서 정렬되어 있지 않다면 정렬을 방해하는 즉, arr[i]>arr[i+1]인 i의 개수를 구해야 한다. 만약 i가 1보다 크다면 어떤 수를 빼도 정렬이 안되기 때문에 이 때 정답은 0이다.

 

정렬을 방해하는 i가 1개라면 i를 기준으로 구간을 나눠서 확인할 필요가 있다. 만약 i+2에 있는 숫자가 i에 있는 숫자보다 같거나 크다면 i+1에 있는 숫자를 뺏을 때 정렬이 가능하다. 만약 i+1에 있는 숫자가 i-1에 있는 숫자보다 같거나 크다면 i에 있는 숫자를 뺏을 때 정렬이 가능하다.

코드

//17074번 정렬.java
package week4;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 정렬_17074 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static int N;
	static int[] arr;
	
	public static int solution() {
		int hill=0;
		int index=0;
		for(int i=0;i<N-1;i++) {
			if(arr[i]>arr[i+1]) {
				index = i;
				hill++;
			}
		}
		if(hill==0)return N;
		if(hill==1) {
			if(index==0) {
				if(arr[index]<=arr[index+2])return 2;
				return 1;
			}
			if(index==N-2) {
				if(arr[index-1]<=arr[index+1])return 2;
				return 1;
			}
			int c=0;
			if(arr[index-1]<=arr[index+1])c++;
			if(arr[index]<=arr[index+2])c++;
			return c;
		}
		return 0;
	}
	
	public static void main(String[] args) throws IOException {
		N = Integer.parseInt(br.readLine());
		arr = new int[N];
		String line = br.readLine();
		StringTokenizer st = new StringTokenizer(line, " ");
		
		for(int i=0;i<N;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		System.out.println(solution());
	}
}