[Backjoon] 통나무 건너뛰기

백준 11497번 통나무 건너뛰기는 그리디 문제로 정렬을 해서 적절한 순서로 통나무들을 배열시키는 문제이다. 기본 아이디어는 우선 통나무들을 정렬시키고 큰 통나무들을 가운데에, 나머지 통나무들을 배열 양쪽 끝쪽으로 배열시키면 되는 것이다. 그 후 가운데서부터 왼쪽 끝, 오른쪽 끝으로 차이를 계산해서 가장 큰 값을 리턴하면 된다.

처음 접근방법은 가운데 값에서 한 개의 차이값들만 계산해서 [1, 2, 3, 4, 5, 100, 101, 102, 103, 104] 같은 예외에서 실패했다. 다른 그리디 문제들을 통해 예외를 생각해보는 연습을 계속해야겠다.

 

import sys
cases = int(input())

for _ in range(cases):
    length = int(input())
    lumbers = list(map(int, input().split(" ")))
    lumbers.sort()

    container = [0 for _ in range(length)]
    idx_container, idx_lumber = 0, 0
    while idx_lumber + 1 < length:
        container[idx_container], container[length-idx_container-1] = lumbers[idx_lumber], lumbers[idx_lumber+1]
        idx_container += 1
        idx_lumber += 2

    if length % 2 == 1:
        container[length//2] = lumbers[length-1]

    diff = 0
    for idx in range(length//2, 0, -1):
        if abs(container[idx] - container[idx-1]) > diff:
            diff = abs(container[idx] - container[idx-1])
            

    for idx in range(length//2, length-1):
        if abs(container[idx] - container[idx+1]) > diff:
            diff = abs(container[idx] - container[idx+1])
            
    print(diff)