[백준 알고리즘] 10819번 Python 풀이

 

완전탐색 - 1476, 1107, 1451, 9095, 10819, 10971, 1697, 1963, 9019, 1525, 2251, 2186, 3108, 5014, 1759, 2580, 1987, 6603, 1182, 2003, 1806, 1644, 1261, 1208, 7453, 2632, 2143

출처: https://plzrun.tistory.com/entry/알고리즘-문제풀이PS-시작하기 [plzrun's algorithm]

알고리즘 문제풀이(PS) 시작하기

 

 

백준 알고리즘 10819번

 

문제를 풀면서 많이 헤맸다.

처음 이 문제를 접근할 때, 모든 경우를 탐색하는 Brute Force 말고, 차이를 최대로 만드는 어떤 로직을 찾으려고 접근했다.
가장 먼저 생각한 차이를 최대로 만드는 상황은 다음과 같다.
1) [최대, 최소, 다음 최대, 다음 최소 ...] or 2) [최소, 최대, 다음 최소, 다음 최대 ...]

그런데, 주어진 예제 입력에 적용해보니 답이 나오지 않았다. 그래서 다른 상황을 고안해본 결과,
양 끝은 한 번 씩만 차이를 구하는데 사용되므로, 3, 4) 양 끝에 중앙값을 배치하고 그 사이에 [최대, 최소, 다음 최대, 다음 최소...]순으로 배치하는 것이었다.

이를 시각화하면 다음과 같다.

결과를 살펴 보면, 중앙값을 양 끝에 배치한 4번에서 실제로 예제 출력이 도출되는 것을 볼 수 있다.

그러나, 검증을 위해 하나 더 예시를 만들어 테스트를 해보니, 이번엔 1) 케이스에서 최대값이 나왔다.
ex)1, 15, 2, 8, 3
결국 상황에 따라 차이를 최대를 만드는 배열은 다르고, 내가 고안한 휴리스틱 방법은 틀렸음을 알게 되었다.

[1, 15, 2, 8 3] 테스트 케이스 결과

 

따라서, 문제를 다시 살펴 보고, N의 범위가 충분히 작기 때문에(3<= N <= 8) Brute Force로 접근하게 되었다. 
그런데... Brute Force로 모든 상황을 만든다는 뜻은, 결국 모든 순열을 살펴본다는 것인데, 나는 순열을 어떻게 구해야하는지에서 다시 막혔다.

찾아보니 1. 라이브러리를 사용하는 풀이가 있고, 2.라이브러리를 사용하지 않고 직접 구현할 수 있었다.

 

 

 

첫 번째 풀이(라이브러리 사용)

itertools의 permutations 라이브러리를 사용하면 간단히 구현할 수 있다.
permutations 메소드는 가능한 순열들을 튜플로 생성해 해당 레퍼런스를 반환하는데, 아래 코드에서는 per 변수에 이를 받아 반복문으로 튜플을 꺼내 각 순열마다 차이의 합(s)을 구해 ans 변수를 update시키고 출력한다.

# Library 사용 풀이

from itertools import permutations
import sys

# 주어진 값 입력
n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))

# permutation 저장(per: reference of permutation tuples)
per = permutations(a)
ans = 0

# 순열마다 차이를 더해(s), ans 보다 크면 ans를 update
for i in per:
    s = 0
    for j in range(len(i)-1):
        s += abs(i[j]-i[j+1])
    if s > ans:
        ans = s

print(ans)

 

 

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

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

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

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

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

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)