[알고리즘] LeetCode - Minimum Moves to Equal Array Elements

LeetCode - Minimum Moves to Equal Array Elements

문제 설명

Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n - 1 elements by 1.

Example 1

Input:
[1,2,3]
Output:
3
Explanation:
Only three moves are needed (remember each move increments two elements):
[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]

Constraint

  • 1 <= nums.length <= 3 * 104
  • 105 <= nums[i] <= 105

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
let minMoves = function (nums) {
    
    let minimum = nums[0];
    
    let moves = 0;
    let lastIdx = nums.length - 1;

    for (let i = 1; i <= lastIdx; i++){
        if (nums[i] < minimum) {
            minimum = nums[i];
        }
    }
    for (let i = 0; i <= lastIdx; i++){
        moves = moves + nums[i] - minimum;
    }
    return moves;
};

[로직]
1) 제일 큰 수와 제일 작은수의 차만큼 move
=> 첫번째 큰 수를 제외한 나머지 숫자들은 (첫번째수-제일작은수) 만큼 +됨
==> 첫번째수와 제일작은수는 값이 같아지고 나머지는 기존의 제일 작은수와의 차이만큼 여전히 큼
2) 두번째수와 제일작은수의 차만큼 move
=> 첫번째수, 두번째수, 제일작은수는 값이 같아지고 나머지는 기존의 제일 작은수와의 차이만큼 여전히 큼
...

~.~

좋은 웹페이지 즐겨찾기