[리트코드 3736] 모든 배열 원소를 같게 만들기 — 최댓값까지 증가시키기

원제: Minimum Moves to Equal Array Elements III

문제 요약

한 번의 이동으로 배열 원소 하나를 1 증가시킬 수 있을 때, 모든 원소를 같게 만드는 최소 이동 횟수를 반환합니다. 원소를 감소시킬 수는 없으므로 공통값은 현재 최댓값보다 작을 수 없습니다.

조건과 입출력

nums는 정수 배열이며 1 <= nums.length <= 100, 1 <= nums[i] <= 100입니다. 반환값은 모든 원소를 같게 만드는 데 필요한 최소 총 이동 횟수입니다.

예제와 문제 자료

예제 1: nums = [2,1,3]이면 Output: 3입니다. 2를 한 번, 1을 두 번 증가시켜 모두 3으로 만듭니다. 예제 2: nums = [4,4,5]이면 Output: 2입니다. 두 개의 4를 각각 한 번 증가시킵니다.

풀이 아이디어

최종 공통값을 T라고 하면, 증가만 가능하므로 T는 max(nums) 이상이어야 합니다. 이때 필요한 이동 수는 각 원소를 T까지 올리는 횟수의 합, 즉 sum(T - num)입니다. T를 max(nums)보다 더 크게 잡으면 모든 원소가 추가로 증가해야 하므로 이동 수가 늘어납니다. 따라서 최솟값은 최댓값을 공통값으로 선택할 때 얻으며, 각 원소와 최댓값의 차이를 더하면 됩니다.

코드의 핵심

코드는 먼저 m = max(nums)로 공통값으로 삼을 최댓값을 구합니다. answer를 0으로 시작한 뒤, for num in nums에서 각 원소에 대해 answer += m-num을 수행합니다. m-num은 해당 원소를 m까지 올리는 데 필요한 정확한 횟수입니다. 최댓값 원소는 차이가 0이므로 이동 횟수에 더해지지 않습니다.

코드 추적 — nums = [2,1,3]: m = 3입니다. 각 num에 대한 차이는 3-2 = 1, 3-1 = 2, 3-3 = 0이므로 answer는 0 → 1 → 3 → 3으로 바뀌고, 반환값은 3입니다.

제출 코드

class Solution:
    def minMoves(self, nums: List[int]) -> int:
        m = max(nums)
        answer = 0
        for num in nums:
            answer += m-num

        return answer

복잡도

n = len(nums)라 하면 max(nums) 계산과 원소 순회에 각각 배열을 한 번씩 확인하므로 시간 복잡도는 O(n)입니다. 추가 보조 공간은 m, answer, num 등 고정된 수의 변수만 사용해 O(1)입니다. 별도의 결과 배열은 저장하지 않습니다.

복습 포인트

배열 길이가 최소 1이므로 max(nums)를 구할 때 빈 배열을 처리할 필요가 없습니다. 증가만 허용되는 문제이므로 최종값을 최댓값보다 작게 선택할 수 없다는 점이 핵심입니다.

출처

문제 원문