Leet Code - 453. Minimum Moves to Equal Array Elements

예제: 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:

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]

풀이

n개의 숫자가 주어졌을 때, (n-1)개의 숫자를 +1씩 해서 모든 숫자가 같은 값을 같게 하기 위한 최소 step 수를 반환하는 문제이다.

필자에게는 굉장히 어려운 문제였다.

얼핏 보면 쉽지만(반복문으로 푼다면) 계속해서 time limited에 걸려서 이 문제는 규칙을 찾는 문제라는게 느껴졌다.

아이큐 문제 중에서도 규칙찾기에 약한 필자에게는 이런 류의 문제는 참 어렵다.

많은 시간을 투자한 끝에 규칙을 찾아냈다.

주어진 숫자의 최소값을 0으로 만들었을 때, 주어진 수의 합 이 답이다.

예를 들어, [1, 2, 3, 4]가 주어졌을 때, 최소값을 0으로 만들면 [0, 1, 2, 3]이다. 그 합은 6이 되는 것이다.

결론만 두고 보면 간단한 규칙이지만, 찾기는 참 어려웠다.
물론 이보다 훨씬 간단하고 빠른 규칙이 존재 할 것이다.

전체적인 소스코드는 아래와 같다.

소스 코드

class Solution {
public:
	int minMoves(vector<int>& nums) {

		long res = 0;
		int minimum = nums[0];
		for (auto n : nums) {
			res += n;
			minimum = min(minimum, n);
		}

		return res - minimum * nums.size();
	}
};

풀이 후기

이게 어떻게 easy야!!!!😱