원제: Minimum Moves to Equal Array Elements II
| 플랫폼 | 문제 번호 | 난이도 | 언어 |
|---|---|---|---|
| 리트코드 | 462 | 보통 (Medium) | Python 3 |
한 번의 이동으로 원소 하나를 1만큼 증가시키거나 감소시킬 수 있을 때, 모든 원소를 같게 만드는 최소 이동 횟수를 구합니다. 제출 코드는 정렬한 뒤 중앙값 하나를 목표값으로 선택하고, 각 원소와의 차이의 절댓값을 더해 반환합니다.
입력은 정수 배열 nums이며 n == nums.length, 1 <= nums.length <= 10^5, -10^9 <= nums[i] <= 10^9입니다. 반환값은 필요한 최소 이동 횟수이고, 정답은 32비트 정수 범위에 들어갑니다. 한 번의 이동은 원소 하나를 1 증가시키거나 1 감소시키는 것입니다.
예제 1: nums = [1,2,3]이면 반환값은 2입니다. 모두 2로 맞추려면 1과 3을 각각 한 번씩 이동합니다. 예제 2: nums = [1,10,2,9]이면 반환값은 16입니다.
목표값을 x라고 하면 필요한 이동 횟수는 모든 원소에 대해 abs(x-num)을 더한 값입니다. 이 합은 정렬된 배열의 중앙값을 목표로 삼을 때 최소가 됩니다. 목표값을 중앙값보다 왼쪽이나 오른쪽으로 옮기면, 그 이동 방향의 원소들에서 줄어드는 거리보다 반대편 원소들에서 늘어나는 거리가 더 커지지 않으므로 합이 더 작아질 수 없습니다. 코드에서는 nums.sort()로 정렬한 뒤 x = nums[n//2]를 사용합니다. 원소 수가 짝수이면 두 중앙값 중 오른쪽 값을 택하지만, 두 값 사이 어느 곳을 목표로 해도 최소 합은 같으므로 이 선택도 유효합니다.
제출 코드는 먼저 n = len(nums)로 원소 수를 저장하고 nums.sort()로 배열을 오름차순 정렬합니다. 이후 x = nums[n//2]를 목표값으로 정하고, for num in nums에서 answer += abs(x-num)을 누적합니다. 각 항은 해당 원소를 x까지 옮기는 데 필요한 횟수이므로, 전부 더한 answer를 반환합니다.
예제 1의 코드 추적: 정렬 결과는 [1,2,3], n//2는 1이므로 x = 2입니다. 거리의 합은 abs(2-1) + abs(2-2) + abs(2-3) = 1 + 0 + 1 = 2입니다.
예제 2의 코드 추적: 정렬 결과는 [1,2,9,10], n//2는 2이므로 x = 9입니다. 거리의 합은 abs(9-1) + abs(9-2) + abs(9-9) + abs(9-10) = 8 + 7 + 0 + 1 = 16입니다.
class Solution:
def minMoves2(self, nums: list[int]) -> int:
n = len(nums)
nums.sort()
x = nums[n//2]
answer = 0
for num in nums:
answer += abs(x-num)
return answer
정렬에 O(n log n), 정렬 뒤 합산에 O(n)이 걸려 전체 시간 복잡도는 O(n log n)입니다. nums.sort()는 입력 배열 자체를 정렬하며, Python 정렬의 보조 공간은 최악의 경우 O(n)입니다. 결과는 정수 answer 하나로 누적하므로 결과 저장 공간은 O(1)입니다.
nums 자체를 정렬하므로 호출 뒤 배열의 순서는 바뀝니다. n >= 1이므로 nums[n//2]는 항상 유효한 인덱스입니다. 짝수 길이에서는 코드가 오른쪽 중앙값을 선택하지만 최소 이동 횟수는 동일합니다.