[Python] 백준 11497번 - 통나무 건너띄기

1. 문제정보

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

11497번: 통나무 건너뛰기

 

 

2. 해결전략

단순히 정렬로만 해결할 수 없는 게 시작점과 끝점이 이어지면서 가장 작은 값과 가장 큰 값으로 인해 최대 레벨로 계산되기 때문이다. 시작점과 끝점의 차이를 줄이는 것이 최선의 전략으로 판단했고 정렬된 값을 하나는 좌측부터, 하나는 우측부터 채워나가면서 새로운 리스트를 만들어서 해결했다.

 

 

3. 코드

t = int(input())

for _ in range(t):
    n = int(input())
    heights = list(map(int, input().split()))
    heights.sort()

    arr = [0]*n

    # 투 포인터
    start = 0
    end = n-1
    for i in range(0, n):
        if i % 2 == 0:
            arr[start] = heights[i]
            start += 1
        else:
            arr[end] = heights[i]
            end -= 1
    
    result = 0
    for i in range(1, n):
        result = max(result, abs(arr[i]-arr[i-1]))
    print(result)