파이썬으로 배열 요소를 같게 만드는 최소 이동 횟수 구하기 (Equal Array Elements II)

문제 개요

비어 있지 않은 정수 배열이 주어졌을 때, 모든 배열 요소를 동일한 값으로 만들기 위해 필요한 최소 이동 횟수를 구하는 문제입니다. 여기서 한 번의 이동(move)이란 선택한 요소의 값을 1만큼 증가시키거나 감소시키는 것을 의미합니다.

예를 들어 배열이 [1, 2, 3]이라면 출력값은 2가 됩니다. 1을 2로 증가시키고, 3을 2로 감소시키면 총 2번의 이동으로 모든 요소를 2로 맞출 수 있기 때문입니다.

해결 접근 방식

이 문제의 핵심은 중앙값(median)에 있습니다. 모든 요소를 중앙값으로 맞추는 것이 다른 어떤 값보다 총 이동 거리를 최소화하기 때문입니다. 해결 단계는 다음과 같습니다.

• 배열 nums를 오름차순으로 정렬합니다.
• 카운터(counter)를 0으로 초기화합니다.
• 배열의 각 요소 i에 대해 다음을 반복합니다.
  • counter에 |i − nums[len(nums) // 2]| (각 요소와 중앙값의 차이의 절댓값)를 더합니다.
• counter 값을 반환합니다.

파이썬 구현 예제

아래 코드를 통해 더 자세히 이해해 보겠습니다.

class Solution:
    def minMoves2(self, nums):
        nums.sort()
        counter = 0
        for i in nums:
            counter += abs(i - nums[len(nums)//2])
        return counter

ob1 = Solution()
print(ob1.minMoves2([2,5,3,4]))

입력

[2,5,3,4]

출력

4

동작 원리 설명

입력 배열 [2, 5, 3, 4]를 정렬하면 [2, 3, 4, 5]가 되고, 중앙값 위치(len(nums)//2 = 2)의 값은 4입니다.

• |2 − 4| = 2
• |3 − 4| = 1
• |4 − 4| = 0
• |5 − 4| = 1

따라서 총 이동 횟수는 2 + 1 + 0 + 1 = 4가 됩니다.

시간 복잡도

정렬에 O(n log n), 순회에 O(n)이 소요되므로 전체 시간 복잡도는 O(n log n)입니다. 정렬 대신 quickselect 알고리즘을 사용하면 평균 O(n)으로 중앙값을 찾아 성능을 더 개선할 수 있습니다.