[백준] (10819) 차이를 최대로 [Python]

🔗 문제 링크

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

문제

N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.

|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|

입력

첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.

테스트 케이스

예제 입력	예제 출력
6 20 1 15 8 4 10	62

💻 나의 코드

1st Code

import random

def cal(arr):
    answer = 0
    for i in range(n-1):
        answer += abs(arr[i] - arr[i+1])
    return answer

n = int(input())
arr = list(map(int, input().split()))
max_val = cal(arr)

for _ in range(10000):
    random.shuffle(arr)
    max_val = max(max_val, cal(arr))

print(max_val)

📝 코드 리뷰

처음에 문제를 풀었을 때는, 배열 내의 모든 수를 뒤섞는 로직의 구현에 실패해서, 그 대안으로 충분히 많은 횟수(10000회)로 배열을 랜덤하게 shuffle시켜서 계산해야 하는 값의 최대값을 구했다. 코드 자체는 정답 처리를 받았지만, 만약 10000회의 연산 중에서 계산을 했을 때 최대값(위의 예제에서는 62)이 나오는 배열 순서가 등장하지 않았더라면 오답 처리를 받았을 것이다. 실제로 셔플 횟수를 1000회 정도로만 설정을 했을 때는 오답 처리를 받았다.

2nd Code

def cal(arr):
    answer = 0
    for i in range(n-1):
        answer += abs(arr[i] - arr[i+1])
    return answer

def shuffle():
    if len(stack) == n:
        global max_val
        
        tmp = list()
        for i in range(n):
            tmp.append(arr[stack[i]])
        
        max_val = max(max_val, cal(tmp))
        del tmp
        return
    
    for i in range(n):
        if i not in stack:
            stack.append(i)
            shuffle()
            stack.pop()

n = int(input())
arr = list(map(int, input().split()))
max_val = cal(arr)

stack = list()
shuffle()

print(max_val)

📝 코드 리뷰

shuffle() 이라는 재귀함수를 추가해서 n! 번 배열의 순서를 뒤섞는 로직을 만들어서 코드를 제출했더니 정답 처리를 받았다. 두 번째 코드의 실행시간은 첫 번째 코드보다 14% 정도 더 오래 걸렸지만, 메모리 사용량은 12% 정도 감소했다.