[백준 문제 복습] 10819번 차이를 최대로 (파이썬)
[백준 문제 복습] 10819번 차이를 최대로 (파이썬)
[백준 문제] 10819번 차이를 최대로를 풀어본다.
나의 생각의 흐름
- 이전에 풀었던 문제를 풀 수 있을까 궁금했다. 이태원클라쓰 막방 보면서 5분안에 쉽게 풀은거 같다.(다음순열 함수를 외웠다는 가정하에..)
- 다음 순열 함수를 이용한다.
- 리스트를 정렬하고 차례대로 순열마다의 공식을 계산한다.
내 풀이
def next_permutation(a):
n = len(a) - 1
i = n
while i > 0 and a[i-1] >= a[i]:
i -= 1
if i == 0: # 마지막 순열
return False
j = n
while a[i-1] >= a[j]: # 오른쪽에 있으면서 a[i-1]보다 큰 수
j -= 1
a[i-1], a[j] = a[j], a[i-1] # SWAP
j = n
while i < j:
a[i], a[j] = a[j], a[i] # a[i]부터 순열 뒤집기
i += 1
j -= 1
return True
n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
big = 0
while True :
sum = 0
for i in range(1,n):
sum += abs(a[i-1]-a[i])
big = max(big, sum)
if next_permutation(a) is True:
continue
else :
break
print(big)
