백준 11497번
https://www.acmicpc.net/problem/11497

문제

후기

⏰ 풀이시간 40분 ++⏰

높이를 단순하게 정렬하는 것이 아니라, 통나무 간의 간격을 생각하며 배열해야 하는 부분에서

알고리즘을 떠올리는 데 꽤 오랜 시간이 걸렸다.

가장 주요했던 생각은

크기가 작은 통나무들을 순서대로 가운데로 몰아서 정렬하다 보면

최대한 차이가 적게 나게 된다

이런 기본 생각을 바탕으로 코드를 구현했고, 정답이 나왔다. 원형으로 이루어진 리스트라고

생각해야 하기 때문에, 마지막에는 첫 번 째의 리스트 값과, 마지막 리스트 값을 비교하는 과정을

반드시 해주어야 한다.

나의 풀이

import sys

input = sys.stdin.readline


for _ in range(int(input())):

    N = int(input())

    li = sorted(list(map(int,input().split())))

    # 크기가 작은 통나무들을 계속 가운데로 순서대로 몰아서 정렬하다 보면 결국 가장 차이가 적지 않을까라는 생각으로 구현

    ans_li = [] #재배열될 리스트

    n= 0

    for i in li:

        if n%2==0:

            ans_li.insert(0+n,i)
        
        else:

            ans_li.insert(-1-n,i)
        
        n+=1
    
    result = 0

    for i in range(0,len(ans_li)-1):  # i번째 통나무와 i+1번째 통나무 비교

        if abs(ans_li[i]-ans_li[i+1]) > result:

            result = abs(ans_li[i]-ans_li[i+1])
        
    if abs(ans_li[0]-ans_li[-1])>result:  #첫번째 통나무와 마지막 통나무 까지 비교해줘야한다.

        result = abs(ans_li[0]-ans_li[-1])

    
    print(result)  #최대값 출력