백준 문제풀기 [#10819번] - 차이를 최대로

 

 

 처음 풀었던 방법 

어떤 개념을 써야하겠다라는 생각을 하지 못하고 막연히 생각하였다. 

몇번 예제로 최대 차이를 구하다보니 중간값이 1번째 배열의 위치에서 시작하여 나머지 값들을 for문으로 돌아가면서 첫번째 값과의 차이를 구하여 제일 차이가 많이 나는 값이 그 다음 배열에 위치하도록 풀어나갔다. 

 

처음 짰던 코드이다. 

import sys

N = int(sys.stdin.readline())
count = 0
plus = 0
result2 = 0

A = list(map(int, sys.stdin.readline().split()))

A.sort()
print(A)
if N % 2 == 0:
    k = int(N/2)
    A[k], A[0] = A[0], A[k]
else:
    k = int(N/2)+1
    A[k], A[0] = A[0], A[k]

for i in range(0, N):
    plus = plus + 1
    count = 0
    for j in range(plus, N):
        result = abs(A[i] - A[j])
        if count < result:
            A[i+1] = A[j]
            count = result
    result2 = result2 + count

print(result2)

너무 엉터리 코드였다. 

 

 

풀이를 본 결과 순열을 이용하여 풀면 훨씬 더 쉽게 풀 수 있다는걸 알게되었다. 

 

순열

 서로 다른 n개에서 r개를 선택하는데 이때 순서를 고려하고 , 중복없이 뽑을 경우의 수를 말한다. 

ex.) A , B, C, D를 순열로 구하여라.

AB/AC/AD/BA/BC/BD/CA/CB/CD/DA/DB/DC

 

코드 사용법 

1. import itertools 

2. permutations(반복 가능한 객체, r) 

 

from itertools import permutations

for i in permutations([1,2,3,4], 2):
    print(i)
    
=> (1, 2) (1, 3) (1, 4) (2, 1) (2, 3) (2, 4) (3, 1) (3, 2) (3, 4) (4, 1) (4, 2) (4, 3)

 

순열을 사용하여 문제 풀기

문제에서 배열을 적절히 순서를 바꿔서 최댓값을 출력하라고 하였다.  배열에 담긴 수들을 하나씩 바꾸지 않고

리스트에 들어있는 n개를 한번에 다 바꿔버리는 순열을 사용한다. 

(예를 들어, 배열에 [1,2,3,4,5,6]이 담겨있으면 permutations[배열 이름, 6) 이런식으로 모든 배열의 값을 순서를 바꾸는 것이다.)

그 모든 경우의 수를 각각 차이를 구하고 그 경우의 수들 중 가장 최대로 차이가 많이 나는 값을 출력하면 된다. 

 

import itertools
import sys

answer = 0
n = int(sys.stdin.readline())  #6 
A = list(map(int, sys.stdin.readline().split()))  # 20 1 15 8 4 10

# 순열 사용 
permu = itertools.permutations(A, n)
# permu 출력 값
# [(20, 1, 15, 8, 4, 10), (20, 1, 15, 8, 10, 4), (20, 1, 15, 4, 8, 10), 등등...]

for p in list(permu):
    sumNum = 0
    for i in range(n-1):
        sumNum += abs(p[i] - p[i+1])
    if sumNum > answer:
        answer = sumNum

print(answer)