문제
남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 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이다. 이 배열보다 난이도가 낮은 배열은 만들 수 없으므로 이 배열이 남규가 찾는 답이 된다
코드
import sys
input = sys.stdin.readline
tc = int(input())
for _ in range(tc):
n= int(input())
arr = list(map(int, input().split()))
arr.sort()
ans = 0
for a in range(0,len(arr)-2):
ans = max(ans, arr[a+2] - arr[a])
print(ans)설명
먼저 주어진 숫자들을 오름차순으로 정렬한다. 그 다음 가장 작은 숫자 부터 차례로 외곽에 치하면 난이도가 가장 낮은 배열을 만들 수 있다. 예를 들자면 문제에 나와 있는 예시를 보면
13 10 12 11 10 11 12
이 숫자들을 먼저 오름차순으로 정렬한다.
10 10 11 11 12 12 13
이 되는데 이제 가장 낮은 숫자 (10)부터 차례로 외곽부터 채워나간다.
10 11 12 13 12 11 10
이렇게 배치하면 인접한 숫자들의 차가 최소가 되는 배열이 된다.
아예 정렬을 이렇게 만들어 놓고 옆에 있는 숫자들의 차를 구하는 반복문을 한 번 더 할 수 있지만 그렇게 되면 비효율 적이게 된다. 완성된 숫자들을 보면 10과 11은 인덱스 0, 2이다. 그 다음 11과 12는 2와 4이다. 즉 오름차순으로 정렬한 후에 인덱스 2 차이 나는 원소와의 차를 구하면 답을 구할 수 있다.
