문제설명
수열을 입력받고 그 수열들을 재배치해서 인접한 수들의 차이의 최대값이 가장 작도록 할 때 그 배치에서의 최대 차이를 구하는 문제입니다.(0번과 N번은 인접한것으로 취급합니다.)
작동 순서
1. 테스트 회수를 입력받습니다.
2. 수열의 길이를 입력받습니다.
3. 수열을 정렬합니다.
4. 만약 1번부터 5번까지의 수열이 있을 경우 (1, 3), (2, 4), (3, 5), (4, 5) 이런식으로 번갈아가면서 배치를 하는 경우가 차이의 최대값을 가장 작게 만드는 방법입니다.
5. 1번부터 N번까지 위의 방식을 이용해 각 인접 수들간의 차이를 구하고 그 중 최대값을 출력합니다.
소스코드
import sys
T = int(sys.stdin.readline())
for i in range(T):
N = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
arr.sort()
maxDiff = arr[1]-arr[0]
frontPivot = 0
backPivot = 2
for j in range(N-1):
maxDiff = max(maxDiff, arr[backPivot]-arr[frontPivot])
frontPivot += 1
if backPivot < N-1:
backPivot += 1
print(maxDiff)