[Python | 11497] 통나무 건너뛰기

https://www.acmicpc.net/problem/11497

---

문제 설명

남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 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이다. 이 배열보다 난이도가 낮은 배열은 만들 수 없으므로 이 배열이 남규가 찾는 답이 된다.

 

📌 시간 제한: 1초

---

입력

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

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

---

출력

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

---

문제 접근

통나무들은 원형으로 배치된다. 즉, 처음과 마지막 통나무도 서로 이웃이다. 이때, 인접한 두 통나무 사이의 높이 차를 모두 계산해서 그 중 최댓값을 구할 때, 이 최댓값이 가장 작아지도록 통나무를 배치하는 것이 목표다.

예를 들어 높이가 [1, 2, 3, 4, 5]인 통나무가 있다면, 단순히 정렬된 순서로 배치하면 5 - 1 = 4 같은 큰 차이가 생긴다. 이런 큰 차이를 줄이기 위해 우리는 좀 더 균형 잡힌 배치를 고민해야 한다.

💡 풀이 접근: 그리디 알고리즘

이 문제는 결국, 가장 높은 통나무가 어느 위치에 오느냐에 따라 전체 구조가 좌우된다. 여기서 떠오른 전략은, 통나무를 가운데에서 바깥쪽으로 번갈아 배치하는 방식이다.

즉, 통나무를 오름차순 정렬한 뒤:

• 가장 낮은 통나무부터 번갈아 왼쪽과 오른쪽에 배치한다.
• 이렇게 하면 가장 큰 통나무는 중앙으로 몰리게 되어, 양쪽 높이 차가 비슷해지고 최대 차이가 최소화된다.

이 전략은 대표적인 Greedy(탐욕법) 방식이다. 매 순간 가장 작은 통나무부터 적절한 위치에 배치함으로써 전체 최적 결과를 유도한다.

📌 구현 핵심 포인트

• 정렬: 통나무 높이를 오름차순 정렬
• 배치 전략: 인덱스 i가 짝수면 왼쪽에, 홀수면 오른쪽에 배치
• 최대 높이 차 계산: 원형이므로 arr[N-1]과 arr[0]도 인접함을 고려해야 함

---

구현

• 원형 배치는 처음과 끝이 연결된다는 점을 고려해야 한다.
• 높이 차를 줄이기 위해서는 양끝이 아닌 중앙에 가장 큰 통나무가 위치해야 한다.
• 그리디한 방식으로 정렬 후 양옆으로 번갈아 배치하면, 자연스럽게 높이 차를 균형 있게 분산할 수 있다.

T = int(input())

for _ in range(T):
    N = int(input())
    logs = list(map(int, input().split()))
    logs.sort()

    # 양옆 번갈아 배치 -> 인접한 통나무 간의 높이차가 최소화됨
    arr = [0] * N # 통나무 순서 저장 리스트
    left, right = 0, N - 1 # 왼쪽에서부터, 오른쪽에서부터
    for i in range(N): # 작은 높이부터 log[i]
        if i % 2 == 0: # 짝수(왼쪽 배치)
            arr[left] = logs[i]
            left += 1
        else: # 홀수(오른쪽 배치)
            arr[right] = logs[i]
            right -= 1

    max_diff = 0
    for i in range(N):
        diff = abs(arr[i] - arr[(i+1)%N]) # 원형 구조
        max_diff = max(max_diff, diff)

    print(max_diff)