파이썬(Python)으로 배열의 편차를 최소화하는 프로그램 구현하기

문제 설명

배열 nums가 주어졌다고 가정해 보겠습니다. 이 배열의 임의의 원소에는 다음 두 가지 연산을 원하는 만큼 반복해서 적용할 수 있습니다.

짝수 원소라면 2로 나눕니다.
홀수 원소라면 2를 곱합니다.

여기서 배열의 편차(deviation)란 배열 안에서 두 원소 간의 최대 차이, 즉 최댓값과 최솟값의 차이를 의미합니다. 우리가 구해야 할 값은 위 연산들을 적절히 수행한 후 배열이 가질 수 있는 최소 편차입니다.

예를 들어 입력이 nums = [6,3,7,22,5]라고 해보겠습니다. 첫 번째 연산에서 홀수인 3에 2를 곱해 배열을 [6,6,7,22,5]로 만들고, 두 번째 연산에서 5에 2를 곱해 [6,6,7,22,10]으로 만듭니다. 마지막으로 짝수인 22를 2로 나누어 [6,6,7,11,10]으로 만들면, 이때 편차는 11 − 6 = 5가 됩니다. 따라서 출력은 5입니다.

해결 전략

핵심 아이디어는 다음과 같습니다. 홀수에 2를 곱하면 짝수가 되지만, 짝수를 계속 2로 나누다 보면 결국 홀수가 됩니다. 즉, 각 숫자가 도달할 수 있는 값의 범위는 정해져 있으므로, 힙(heap) 자료구조를 활용해 현재 최솟값과 최댓값을 효율적으로 추적하면서 가능한 모든 경우 중 최소 편차를 찾아내는 것입니다.

이 문제는 다음 단계를 거쳐 해결할 수 있습니다.

리스트 nums를 정렬합니다.
max_v := nums의 최댓값
min_v := nums의 최솟값
nums를 최소 힙(min-heap)으로 변환(heapify)합니다.
res := max_v − min_v (초기 편차)
nums[0], 즉 현재 최솟값이 홀수인 동안 다음을 반복합니다.
- v := 힙 큐 nums에서 원소를 하나 꺼냅니다(pop).
- v := 2 × v 로 값을 두 배로 만듭니다.
- v를 힙 큐 nums에 다시 삽입(push)합니다.
- min_v := nums[0]
- max_v := v와 max_v 중 더 큰 값
- res := res와 (max_v − min_v) 중 더 작은 값
nums의 모든 원소를 음수로 바꾼 새 리스트를 만듭니다.
변경된 nums를 다시 힙으로 변환합니다. (이렇게 하면 최대 힙처럼 동작합니다.)
nums[0]이 짝수인 동안 다음을 반복합니다.
- v := −(힙 큐 nums에서 꺼낸 원소)
- v := v ÷ 2의 몫 (v // 2)
- −v를 힙 큐 nums에 삽입합니다.
- max_v := −nums[0]
- min_v := min_v와 v 중 더 작은 값
- res := res와 (max_v − min_v) 중 더 작은 값
res를 반환합니다.

예제 구현

더 잘 이해할 수 있도록 다음 파이썬 구현 예제를 살펴보겠습니다.

import heapq
def solve(nums):
   nums.sort()
   max_v,min_v = nums[-1],nums[0]
   heapq.heapify(nums)
   res = max_v-min_v
   while nums[0]%2==1:
      v = heapq.heappop(nums)
      v = 2 * v
      heapq.heappush(nums, v)
      min_v = nums[0]
      max_v = max(v, max_v)
      res = min(res, max_v - min_v)

   nums = [-n for n in nums]
   heapq.heapify(nums)
   while nums[0]%2==0:
      v = -heapq.heappop(nums)
      v = v // 2
      heapq.heappush(nums, -v)
      max_v = -nums[0]
      min_v = min(min_v,v)
      res = min(res, max_v - min_v)

   return res

nums = [6,3,7,22,5]
print(solve(nums))

입력

[6,3,7,22,5]