[완전탐색] 백준 10819번 차이를 최대로 with Python3

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

10819번: 차이를 최대로

문제

 

내 풀이

import itertools

n = int(input())
inilist = list(map(float, input().split()))

inilist.sort()

result = list(itertools.permutations(inilist, len(inilist)))


ttlsum = []
for i in range(len(result)):
    inisum = []
    search = []
    search.append(result[i])
    for j in range(len(search[0])):
        if j+1 == len(search[0]):
            break
        a = search[0][j]
        b = search[0][j+1]
        inisum.append(abs(a - b))
    ttl = sum(inisum)
    ttlsum.append(ttl)

ans = int(max(ttlsum))
print(ans)

해설

itertool로 사기치기 2.

완전탐색이 모두 그렇겠지만, 시간복잡도가 최악이다.

이 경우엔 난쟁이랑 다르게 순서가 중요해서 상당히 많은 경우의 수가 담긴 리스트를 만들었다. 

거기다가 그 모든 경우의 수의 주어진 조건(==ttl)을 담아서 그안에서 max()를 돌렸다;

완전 무지성 해결법;

 

 

정답 풀이

import sys
 
 
def next_permutation(list_a):
    k = -1
    m = -1
 
    # 증가하는 마지막 부분을 가리키는 index k 찾기
    for i in range(len(list_a)-1):
        if list_a[i] < list_a[i+1]:
            k = i
 
    # 전체 내림차순일 경우, 반환
    if k == -1:
        return [-1]
 
    # index k 이후 부분 중 값이 k보다 크면서 가장 멀리 있는 index m 찾기
    for i in range(k, len(list_a)):
        if list_a[k] < list_a[i]:
            m = i
 
    # k와 m의 값 바꾸기
    list_a[k], list_a[m] = list_a[m], list_a[k]
 
    # k index 이후 오름차순 정렬
    list_a = list_a[:k+1] + sorted(list_a[k+1:])
    return list_a
 
 
# 주어진 값 입력 & 정렬
n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
a.sort()
 
ans = 0
# 첫 순열 내 값 차이를 더해(s), ans 보다 크면 ans를 update
s = 0
for j in range(len(a) - 1):
    s += abs(a[j] - a[j+1])
if s > ans:
    ans = s
 
arr = a
 
while True:
    arr = next_permutation(arr)
    if arr == [-1]:
        break
    s = 0
 
    # 순열마다 차이를 더해(s), ans 보다 크면 ans를 update
    for j in range(len(arr) - 1):
        s += abs(arr[j] - arr[j+1])
    if s > ans:
        ans = s
 
print(ans)

출처:https://sdesigner.tistory.com/51

 

해석

두 번째 풀이(라이브러리 X)

라이브러리를 사용하면 편하지만, 때로 라이브러리를 사용할 수 없는 상황(Python이 아닌 다른 언어로 구현해야 하는 경우, 사용이 제한된 환경에서 테스트를 응시하는 경우 등...)이 있을 것 같아 라이브러리 없이 순열을 구하는 방법도 알고 싶었다.

 

라이브러리를 사용하지 않고 구하려면, 나리야나 판디타의 다음 순열 알고리즘을 사용해 구현할 수 있다.
다음 순열 알고리즘 10972번과, 10974번을 참고

sdesigner.tistory.com/49
sdesigner.tistory.com/50

 

순열을 구하는 방법을 제외하고 전체적인 틀에서 첫 번째 풀이와 크게 다른 점은 없다.
순열을 구하는 함수가 사전순으로 다음 순열을 구하기 때문에 사전 순 첫 순열을 가지고 먼저 차이를 구해보고,
이후 While문에서 반복적으로 다음 순열의 차이를 구해 차이의 최댓값을 update한다.

 

 

우선 총합 값을 한 리스트에 또 만들어서 한 내 방식이 확실히 틀렸음을 알 수 있다.

 

그냥 if 문을 돌리면 해결되는 것인데;