[리트코드 453] 모든 원소를 같게 만들기 — 최솟값과의 차이 합산

원제: Minimum Moves to Equal Array Elements

문제 요약

한 번의 이동으로 배열에서 n - 1개의 원소를 각각 1씩 증가시킬 때, 모든 원소를 같게 만드는 최소 이동 횟수를 반환합니다. 제출 코드는 배열의 최솟값을 기준으로 각 원소와의 차이를 더합니다.

조건과 입출력

입력 nums는 정수 배열이며 n == nums.length, 1 <= nums.length <= 10^5, -10^9 <= nums[i] <= 10^9입니다. 답은 32비트 정수에 들어갑니다. 이동 한 번마다 배열 원소 n - 1개를 1씩 증가시키며, 반환값은 필요한 최소 이동 횟수입니다.

예제와 문제 자료

예제 1: Input: nums = [1,2,3], Output: 3. 예제 2: Input: nums = [1,1,1], Output: 0.

풀이 아이디어

각 이동에서 증가하지 않는 원소 하나를 기준으로 보면, 다른 원소를 모두 1씩 올리는 것은 상대적으로 그 원소 하나를 1 낮추는 것과 같습니다. 따라서 원소들을 공통으로 올리는 효과를 제외하면, 한 번의 이동은 원소 하나를 1 줄이는 효과로 볼 수 있습니다. 모든 값을 같게 만들 때 목표값을 최솟값보다 높게 잡으면 줄여야 할 양이 더 커지므로, 최소 이동 횟수는 각 원소를 최솟값까지 낮추는 데 필요한 양의 합입니다. 코드의 num - min_num이 각 원소가 최솟값보다 큰 만큼을 나타냅니다.

코드의 핵심

min_num = min(nums)로 기준이 되는 최솟값을 구하고, answer를 0으로 시작합니다. 반복문에서 각 num에 대해 answer += num - min_num을 수행합니다. 최솟값인 원소는 차이가 0이므로 합에 기여하지 않고, 다른 원소는 최솟값과의 차이만큼 이동 횟수에 기여합니다. 예제 1에서는 차이가 각각 0, 1, 2이므로 반환값은 3입니다. 예제 2에서는 모든 차이가 0이므로 반환값은 0입니다.

제출 코드

class Solution:
    def minMoves(self, nums: list[int]) -> int:
        min_num = min(nums)
        answer = 0
        for num in nums:
            answer += num - min_num

        return answer        

복잡도

n을 len(nums)라고 하면 최솟값 탐색과 합산 반복문은 각각 배열을 한 번씩 확인하므로 시간 복잡도는 O(n)입니다. min_num과 answer 외에 입력 크기에 비례하는 자료구조를 만들지 않아 보조 공간은 O(1)입니다. 별도의 결과 배열은 저장하지 않습니다.

복습 포인트

배열 길이는 최소 1이므로 min(nums)를 계산할 수 있습니다. 최솟값 자체가 음수여도 코드의 차이 계산은 그대로 적용됩니다.

출처

문제 원문