크기가 n인 배열이 주어졌을 때, 모든 배열 요소를 동일하게 만들기 위해 필요한 최소 이동 횟수를 구하는 문제입니다. 여기서 한 번의 '이동'은 n - 1개의 요소를 1씩 증가시키는 연산을 의미합니다.
예를 들어 입력 배열이 [3, 2, 3, 4]라면, 필요한 최소 이동 횟수는 4입니다.
핵심 아이디어
이 문제의 핵심은 관점을 바꾸는 것입니다. n - 1개의 요소를 1씩 올리는 것은, 상대적인 차원에서 보면 나머지 하나의 요소를 1씩 내리는 것과 수학적으로 동일합니다. 따라서 모든 요소가 같아질 때까지 각 요소를 최솟값까지 낮추는 데 필요한 연산 횟수, 즉 각 요소와 최솟값의 차이의 합이 곧 정답이 됩니다.
해결 절차
n := nums의 크기로 설정합니다.
n이 0이라면 0을 반환합니다.
배열 nums를 오름차순으로 정렬합니다.
ans := 0으로 초기화합니다.
i를 0부터 n 미만까지 반복하며 다음을 수행합니다:
ans := ans + (nums[i] - nums[0])
ans를 반환합니다.
배열을 정렬하면 첫 번째 요소(nums[0])가 곧 최솟값이 되므로, 각 요소에서 이 값을 빼고 모두 더하면 원하는 답을 얻을 수 있습니다.
예제 코드
다음 C++ 구현을 통해 더 쉽게 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minMoves(vector<int>& nums) {
int n = nums.size();
if (n == 0)
return 0;
sort(nums.begin(), nums.end());
int ans = 0;
for (int i = 0; i < n; i++) {
ans += nums[i] - nums[0];
}
return ans;
}
};
main(){
Solution ob;
vector<int> v = {3,2,3,4};
cout << (ob.minMoves(v));
}입력
{3,2,3,4}출력
4
복잡도 분석
정렬에 O(n log n)의 시간이 소요되고, 이후의 순회는 O(n)이므로 전체 시간 복잡도는 O(n log n)입니다. 추가 공간은 상수만 사용하므로 공간 복잡도는 O(1)입니다. 참고로 정렬 없이 최솟값만 한 번의 순회로 찾으면 O(n) 시간에 해결할 수도 있습니다.