백준 10819 [차이를 최대로] 파이썬

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

10819번: 차이를 최대로

import sys
input = sys.stdin.readline

N = input().rstrip()
sum = 0
answer = 0
lst = list(map(int, input().split()))
lst.sort()
slst = lst[:len(lst)//2]
lst = lst[len(lst)//2:]
i = -1
for i in range(len(slst)-1):
    sum += lst[i]-slst[i]
    sum += lst[i+1]-slst[i]
i += 1
sum += lst[i]-slst[i]
if len(lst) != len(slst):
    sum += lst[i+1]-slst[i]

answer = max(sum, answer)
sum = 0
lst.append(lst.pop(0))
i = -1
for i in range(len(slst)-1):
    sum += lst[i]-slst[i]
    sum += lst[i+1]-slst[i]
i += 1
sum += lst[i]-slst[i]
if len(lst) != len(slst):
    sum += lst[i+1]-slst[i]

answer = max(sum, answer)

print(answer)

다음과 같은 방식으로 문제를 해결하려고 하였으나, 예외 케이스가 발생하여서 실패했다 ㅠㅠ

 

#10819
import sys, itertools

# 입력
n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))

# 순열
permu = itertools.permutations(data, n)

# 차이가 최대인 값을 넣을 변수
answer = 0

for p in list(permu):
    # 차이의 합을 저장하는 임시 변수
    sumNum = 0

    # 차이의 합 계산
    for i in range(n-1):
        sumNum += abs(p[i]- p[i+1])

    # 차이의 합 최대값 비교
    if sumNum > answer:   # answer = max(sumNum, answer) - 실행시간이 더 걸림
        answer = sumNum

print(answer)

다른분의 풀이를 참고하여 해결하였다. 

순열을 이용하여 모든 경우의 수를 체크해본다.