경이로운 그리디 알고리즘 5 -인접한 원소간 차이의 최댓값을 최소로 만드는 방법-

1. 문제

 

11497번: 통나무 건너뛰기 (acmicpc.net)

11497번: 통나무 건너뛰기

 

2. 풀이

 

요약하자면 인접한 원소간 차이의 최댓값이 최소가 되도록 배열을 정렬할때, 그 최솟값을 구하는 문제

 

단순히 크기 순으로 정렬한다고 하더라도..

 

[a1,a2,a3,...,an]에서 인접한 원소간 차이의 최댓값은 an-a1이므로, 배열의 최댓값과 최솟값의 차이이므로 이것이 최소일리는 없다

 

만약 크기순으로 정렬한다면, a1 < a2 < a3 < ... < an일때, 이들이 인접했을때, 원소간 차이가 작을 가능성이 높다.

 

다시 말해, a1은 양 옆에 a2, a3가 있을때 가장 유리하다.

 

[a2,a1,a3] 이런 식으로

 

a2는 양 옆에 a1,a3가 있을때 유리하지만 a3는 a2옆에 있을 수 없으니 적어도 a4가 와줘야한다

 

[a1,a3,....,a4,a2]

 

a3는 양 옆에 a2,a4가 있을때 유리하지만 a2나 a4는 있을 수 없으니 못해도 a1,a5까지 양 옆에 있어줘야 유리하고,

 

a4도 마찬가지로 a6까지는 옆에 있어줘야 유리하다

 

[a1,a3,a5,.....,a6,a4,a2]

 

이런 식으로 배열을 정렬해서 가장 작은 원소 a1부터 시작해서 양 끝에 번갈아 배치하면

 

모든 인접한 원소간 거리가 최대 2인덱스이내가 되도록 만들 수 있다

 

혹은 반대로, 가장 큰 원소를 중앙에 두고 [an]

 

양 옆에 그 다음 원소를 번갈아 두고 [an-1,an,an-2]

 

또 양 옆에 그 다음 원소를 번갈아 두고 [an-3,an-1,an,an-2,an-4]...

 

이런식으로 해도 똑같은거

 

그래서 이렇게 정규분포 모양으로 배치할때, 모든 원소간 차이가 최대 2인덱스 이내가 되므로 가장 유리해진다.

 

1인덱스 이내로 만들고자 한다면... [a1,a2,...,an]인데.. an과 a1의 차이가 매우 커지므로 오답이 된다

 

 

 

from collections import deque
from sys import stdin

T = int(stdin.readline())

for _ in range(T):
    
    n = int(stdin.readline())
    A = list(map(int,stdin.readline().split()))

    A.sort()

    B = deque([A.pop()])

    flag = True

    while A:
        
        if flag:

            B.append(A.pop())
            flag = False
        
        else:
            
            B.appendleft(A.pop())
            flag = True
    
    answer = abs(B[0]-B[-1])

    for i in range(n-1):
        
        if abs(B[i] - B[i+1]) > answer:
            
            answer = abs(B[i]-B[i+1])
    
    print(answer)

 

 

deque가 조금 불편하면.. 인덱스로 이렇게 접근할수도 있을듯

 

from sys import stdin

#인접한 원소간 차이의 최댓값이 최소가 되도록 배치하는 방법
#배열을 정렬하고, 가장 작은 원소부터 왼쪽 끝, 오른쪽 끝에 번갈아 배치한다

T = int(stdin.readline())

for _ in range(T):
    
    n = int(stdin.readline())

    A = list(map(int,stdin.readline().split()))

    A.sort()

    B = [0]*n

    left = 0
    right = n-1

    for i in range(n):
        
        if i % 2 == 0:

            B[left] = A[i]
            left += 1

        else:

            B[right] = A[i]
            right -= 1
    
    answer = B[-1] - B[0] #오른쪽이 더 큰 값으로 배치해둠

    for i in range(n):

        k = abs(B[i] - B[i-1]) 

        if k > answer:
            
            answer = k
    
    print(answer)