[백준 | Python] #16209 - 수열 섞기

16209번: 수열 섞기

문제

길이가 $N$인 수열 $a_1,…,a_N$을 재배열 했을 때 인접한 원소의 곱들의 합, 즉 $a_1a_2+a_2a_3+…a_{N-1}a_N$이 최대일 때의 재배열 된 수열을 출력하여라.

아이디어

직관적으로 절댓값이 큰 수부터 서로 곱해야 합을 최대로 만들 수 있음을 알 수 있다.

양수는 양수끼리, 음수는 음수끼리 곱하여 최대한 많은 곱을 양수로 만들어야 한다.

0은 최대한 0끼리 곱하고 부득이한 경우 절댓값이 가장 작은 수와 곱한다.

구현

1. 주어진 수열을 정렬한 후 음수, 0, 양수 부분으로 분리한다.
2. 음수, 양수 부분은 절댓값이 큰 수부터 차례로 다음의 규칙을 통해 각각의 양방향 큐(deque)에 추가한다.
   1) 첫 번째 수와 두 번째 수는 그냥 추가
   2) 이후로는 양방향 큐의 양쪽 끝 원소 중 절댓값이 큰 쪽에 추가
3. 0이 포함된 배열의 양쪽에 앞서 만든 두 개의 양방향 큐를 연결하여 출력한다.
   단, 0과 연결되는 쪽은 절댓값이 더 작은 수로 한다.

문제를 해결한 후 생각해보니 2번은 더 간단하게 구현할 수 있었다.

분리된 수열에서 짝수 번째와 홀수 번째를 분리하여 절댓값이 큰 수를 중앙으로 하여 분리된 두 배열을 연결하면 간단하게 해결된다… 양방향 큐도 필요 없다.

그래도 그리디 알고리즘을 굳이 직접 구현했음에 의의를 두는 것이 좋을 것 같다.

코드

원래 떠올렸던 아이디어로 작성한 코드는 아래와 같다.

from collections import deque

n = int(input())
nums = list(map(int, input().split()))
nums.sort() # 오름차순 정렬

negative = deque()
zero = deque()
positive = deque()

# 원소가 음수일 때까지 절댓값이 큰 수부터 음수 양방향 큐에 추가
i = 0
while i < n and nums[i] < 0:
    if len(negative) < 2 or negative[0] > negative[-1]:
        negative.append(nums[i])
    else:
        negative.appendleft(nums[i])
    i += 1

# 원소가 0이면 단순히 zero 배열에 추가
while i < n and nums[i] == 0:
    zero.append(0)
    i += 1

# 원소가 양수일 때까지 절댓값이 큰 수부터 양수 양방향 큐에 추가
j = n-1
while j >= i:
    if len(positive) < 2 or positive[0] < positive[-1]:
        positive.append(nums[j])
    else:
        positive.appendleft(nums[j])
    j -= 1

ans = [] # 최종 출력 리스트

# 절댓값이 작은 수를 가운데로 하여 음수 양방향 큐 추가
if len(negative) < 2 or negative[0] < negative[-1]:
    ans += negative
else:
    ans += reversed(negative)

ans += zero

# 절댓값이 작은 수를 가운데로 하여 양수 양방향 큐 추가
if len(positive) < 2 or positive[0] < positive[-1]:
    ans += positive
else:
    ans += reversed(positive)

print(*ans)

간단한 구현으로 정돈된 코드는 아래와 같다.

n = int(input())
nums = list(map(int, input().split()))
nums.sort()

# 음수
neg_idx = 0
while neg_idx < n and nums[neg_idx] < 0: neg_idx += 1
negative = nums[0:neg_idx:2][::-1] + nums[1:neg_idx:2]

# 양수
pos_idx = n-1
while pos_idx >= 0 and nums[pos_idx] > 0: pos_idx -= 1
positive = nums[pos_idx+1:n:2] + nums[pos_idx+2:n:2][::-1]

# 0
zero = [0] * (pos_idx - neg_idx + 1)

if negative and negative[0] > negative[-1]:
    negative.reverse()
if positive and positive[0] > positive[-1]:
    positive.reverse()

print(*(negative + zero + positive))

번외) 숏코딩

N,*n=map(int,open(0).read().split())
n.sort()
x=len(a:=[i for i in n if i<0])
y=len(b:=[i for i in n if i>0])
print(*((a[-1-x%2::-2]+a[::2])[::x%2*2-1]+[0]*(N-x-y)+(b[y%2::2]+b[::-2])[::1-y%2*2]))

더 줄일 수 있을 것 같지만 머리가 아프다.