[백준] 통나무 건너뛰기 풀이

처음와 끝을 포함한 각 요소들의 차를 최소로 하되, 그 최소중 최댓값을 출력하는 문제였습니다.
사실상 처음과 끝은 무의미하기에, 원형으로 되어 있는 자료구조라고 생각하면 편하겠네요.

원형으로 되어있는 구조기에 어디서 보든 간에 차가 최소가 되어야 하므로, 결국 리스트 기준으로 가운데 요소까지 오름차순으로 되어 있으며, 가운데 이후부터 내림차순으로 되어야 하는 것을 알 수 있습니다.

위의 조건을 만족하기 위해서 가운데에 위치한 요소가 최대가 되어야 하므로 결국 리스트를 오름차순 뒤에 한 요소씩 띄어가며 append하고, append되지 않은 요소들을 내림차순 방향으로 append한 뒤 그 요소들의 차를 0으로 초기화 한 뒤, max 함수를 이용하여 업데이트 하면 됩니다.

리스트 요소의 갯수가 홀수 즉, [1,3,2,4,5] 의 경우 -> [1,2,3,4,5]로 정렬한 뒤, 새로운 리스트에 [1,3,5]를 append하고 [4,2]를 차례대로 append하면 됩니다.

짝수인 경우는 홀수의 경우와 다르게 [1,3,2,4,5,6] -> [1,2,3,4,5,6] 으로 정렬한 뒤, [1,3,5], [6,4,2] 식으로 append하면 됩니다.
최댓값이 나중에 append되긴 하지만 가운데 쪽에 위치하는 것은 변하지 않습니다. for문에서 범위만 조금 바뀌는 정도입니다.

from sys import stdin

T = int(input())

for i in range(T):
    N = int(input())
    poc = []
    arr = list(map(int, stdin.readline().split()))
    arr.sort()
    ans = 0
    
    if N % 2 == 1:
        for j in range(0,len(arr),2):
            poc.append(arr[j])

        for j in range(len(arr)-2,0,-2):
            poc.append(arr[j])
            
    else:
        for j in range(0,len(arr),2):
            poc.append(arr[j])

        for j in range(len(arr)-1,0,-2):
            poc.append(arr[j])
            
    for j in range(len(poc)-1):
        ans = max(ans, abs(poc[j+1] - poc[j]))
        
    ans = max(ans, abs(poc[0] - poc[1]))
    print(ans)