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

나무 건너뛰기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	2406	1333	1104	59.069%

문제

남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 차가 최소가 되게 하려 한다.

통나무 건너뛰기의 난이도는 인접한 두 통나무 간의 높이의 차의 최댓값으로 결정된다. 높이가 {2, 4, 5, 7, 9}인 통나무들을 세우려 한다고 가정하자. 이를 [2, 9, 7, 4, 5]의 순서로 세웠다면, 가장 첫 통나무와 가장 마지막 통나무 역시 인접해 있다. 즉, 높이가 2인 것과 높이가 5인 것도 서로 인접해 있다. 배열 [2, 9, 7, 4, 5]의 난이도는 |2-9| = 7이다. 우리는 더 나은 배열 [2, 5, 9, 7, 4]를 만들 수 있으며 이 배열의 난이도는 |5-9| = 4이다. 이 배열보다 난이도가 낮은 배열은 만들 수 없으므로 이 배열이 남규가 찾는 답이 된다.

입력

입력은 T개의 테스트 케이스로 이루어져 있다. 첫 줄에 T가 주어진다.

이어지는 각 줄마다 첫 줄에 통나무의 개수를 나타내는 정수 N(5 ≤ N ≤ 10,000), 둘째 줄에 각 통나무의 높이를 나타내는 정수 Li가 주어진다. (1 ≤ Li ≤ 100,000)

출력

각 테스트 케이스마다 한 줄에 주어진 통나무들로 만들 수 있는 최소 난이도를 출력하시오.

예제 입력 1

xxxxxxxxxx
3
7
13 10 12 11 10 11 12
5
2 4 5 7 9
8
6 6 6 6 6 6 6 6

예제 출력 1

xxxxxxxxxx
1
4
0

 

 

 

풀이

먼저 입력으로 들어오는 배열을 정렬합니다.

 

그 후 난이도 설정을 위한 배열을 새로 만들어 줍니다.

 

a배열과 b배열이라고 하겠습니다.

 

a배열은 정렬된 원본 배열이고

b배열은 아직 아무것도 들어있지 않습니다.

 

문제의 예시로 나온 입력이 2, 4, 5, 7, 9 이렇게 있을 때

 

더 나은 배열 [2, 5, 9, 7, 4]를 만들 수 있으며 이 배열의 난이도는 |5-9| = 4이다. 이 배열보다 난이도가 낮은 배열은 만들 수 없으므로 이 배열이 남규가 찾는 답이 된다

 

라는 지문이 있습니다

그럼 저기있는 25974는 어떻게 나왔을까요? 이것에 대해서 고민을 해보면 됩니다.

 

정렬된 배열에서 왼쪽에 제일 작은수 하나, 오른쪽에 그 다음 작은수 하나

이렇게 차근차근 진행해주면 됩니다.

 

조금 풀어서 말하자면 배열이 2,4,5,7,9 이렇게 있을 때

답을위한 b배열에 왼쪽에 2를 넣어줍니다

 

0	1	2	3	4
2

0번째 자리에 값을 넣었으니 다음번에 왼쪽에 넣어줘야 하는 값은 1번째 인덱스에 넣어줍니다.

 

 

이제 왼쪽을 한 번 넣어줬으니 오른쪽을 넣어줄 차례입니다. 2,4,5,7,9에서 2를 이미 윗단계에서 사용했으니 이를 제외한 가장 작은값 4를 넣습니다

 

0	1	2	3	4
2				4

 

 

이제 오른쪽도 채워주었으니 다음 오른쪽 채울땐 인덱스 3번에 채워줘야합니다.

 

왼쪽/오른쪽 서로 번갈아가면서 채워 주었으니 이제 다시 왼쪽을 채워줍니다.(2,4,5,7,9 중 2,4는 사용했으니 제외하고 가장 작은수인 5를 넣어줍니다)

 

0	1	2	3	4
2	5			4

 

오른쪽도 마찬가지로 진행해주면 됩니다

0	1	2	3	4
2	5		7	4

 

이렇게 반복하다보면 답이 완성됩니다.

 

전체코드

import java.io.*;
import java.util.*;
import java.math.*;
public class Main {
    static int t,n;
    static int arr[];
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        t = Integer.parseInt(br.readLine());
        
        while(t>0) {
            t--;
            n = Integer.parseInt(br.readLine());
            int min = Integer.MAX_VALUE;
            arr = new int[n];
            String[] t = br.readLine().split(" ");
            for(int i=0; i<n; i++) {
                arr[i] = Integer.parseInt(t[i]);
            }
            
            int ans[] = new int[n];
            int left = 0;
            int right = n-1;
            
            Arrays.sort(arr);
            
            for(int i=0; i<n; i++) {
                if(i%2!=0) {
                    ans[left] = arr[i];
                    left+=1;
                }
                else {
                    ans[right] = arr[i];
                    right-=1;
                }
            }
            min = Math.abs(ans[0]-ans[n-1]);
            for(int i=1; i<n; i++) {
                min = Math.max(min, Math.abs(ans[i]-ans[i-1]));
            }
            System.out.println(min);
        }
        
    }
}
​