[백준] 16193번 차이를 최대로 2 ★★★

💡문제접근

📌 첫 번째 접근한 방법

• 큰 수와 작은 수를 번갈아가면서 뽑아주면 당연히 차이가 최대가 되지 않을까 싶어서 그대로 입력했더니 바로 WA를 받았다.

📌 두 번째 접근 방법

• 이 문제의 알고리즘에 왜 자료 구조가 없었는지 정말 궁금했다.
• 덱(deque)은 배열의 앞과 뒤에서 데이터를 처리할 수 있는 양방향 자료형이다.
• 이 자료 구조를 이용해서 문제를 해결해보려고 시도했다.
  • abs(배열의 마지막 값 - 덱의 마지막 값)
  • abs(배열의 마지막 값 - 덱의 첫 번째 값)
  • abs(배열의 첫 번째 값 - 덱의 마지막 값)
  • abs(배열의 첫 번째 값 - 덱의 첫 번째 값)
• 위의 4가지 경우를 전부 비교해서 덱(deque)에 append하거나 appendleft를 해주었다.

💡코드(메모리 : 153332KB, 시간 : 2012ms)

from collections import deque
import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().strip().split()))
arr.sort()
arr = deque(arr)
q = deque()
q.append(arr.pop())
ans = 0
for i in range(N-1):
    val1 = abs(arr[0] - q[0])
    val2 = abs(arr[0] - q[-1])
    val3 = abs(arr[-1] - q[-1])
    val4 = abs(arr[-1] - q[0])
    Max = max(val1, val2, val3, val4)
    if Max == val1:
        ans += val1
        q.appendleft(arr.popleft())
    elif Max == val2:
        ans += val2
        q.append(arr.popleft())
    elif Max == val3:
        ans += val3
        q.append(arr.pop())
    else:
        ans += val4
        q.appendleft(arr.pop())
print(ans)

💡소요시간 : 40m