악곱 == 악성곱슬

그리디, 정렬

---

그리디 문제는 정렬과 세트로 많이 나온다. 이 문제도 그렇다.

그리디임을 파악하긴 쉽지만, 어떻게 정렬을 해야할지 까다로운 문제중 하나이다.

주어진 리스트에서 홀수, 짝수 나누어서 정렬하고 붙인 후, 완전 탐색하며 매 순간 최대값을 저장하며 풀면 된다.

import sys

def solution(n, li):
    if len(li) == 1:
        return -1
    li.sort()
    odd_li = li[0::2]
    even_li = li[1::2]
    even_li.reverse()
    new_li = odd_li + even_li
    _max = abs(new_li[1] - new_li[0])
    for i in range(1, len(new_li)-1):
        tmp = abs(new_li[i+1] - new_li[i])
        if tmp > _max:
            _max = tmp
    return _max

if __name__ == "__main__":
    T = int(sys.stdin.readline().rstrip())
    for _ in range(T):
        N = int(sys.stdin.readline().rstrip())
        L = list(map(int, sys.stdin.readline().rstrip().split()))
        print(solution(N, L))