[백준OJ] 11497번 통나무 건너뛰기

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

11497번: 통나무 건너뛰기

---

풀이

먼저 통나무를 배치하는 방법에 대해서 문제를 유심히 읽었다. 순차정렬을 한다면 처음과 맨 마지막도 인접해있어서 난이도가 엄청나게 뛰게된다.

그러면 난이도 차이를 최소화 하기위한 배치는 어떻게 될까? 가장 최소화를 할수있는 타협점은 순서대로 좌우 좌우 통나무를 놓으면 된다. 예를들어 아래와같이 높이가 2 4 5 7 9인 통나무가 있다고 해보자.

순서대로 좌우로 놓는다는 의미는 먼저 2를 맨 왼쪽에 두고, 4를 맨 오른쪽에 둔다. 그런뒤 5를 2와 4 사이에 놓고, 7을 5와 4사이에 둔다. 마지막으로 9는 5와 7사이에 두면 최적의 배치가 완성이 되며, 난이도는 4로 최소가 된다.

시간복잡도

입력받는데 O(N), 자바 arrays.sort함수를 사용하여 정렬을 했으므로 O(NlogN), 위의 최적화 배치를 만드는데 O(N), 난이도를 구하는데 O(N)이 걸렸으므로, 총 시간복잡도는 O(TNlogN)이 된다.

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();

        while((t--)>0){
            int n=sc.nextInt();
            int[] array=new int[n];
            int[] array2=new int[n];
            int result=0;
            for(int i=0;i<n;i++){
                array[i]=sc.nextInt();
            }
            Arrays.sort(array);
            for(int i=0;i<n;i++){
                if(i%2==0){
                    array2[i/2]=array[i];
                }
                else{
                    array2[n-1-(i/2)]=array[i];
                }
            }
            for(int i=0;i<n;i++){
                int gap=Math.abs(array2[i]-array2[(i+1)%n]);
                result=Math.max(gap,result);
            }
            System.out.println(result);
        }
        sc.close();
    }
}