[LeetCode] 462. Minimum Moves to Equal Array Elements II

문제링크

배열이 주어졌을 때, 배열 안의 모든 원소들의 값이 같아질 때까지 +1 혹은 -1을 해야하는 최소 횟수를 구하는 문제이다.

먼저 주어진 배열을 sorting해서 중간값을 구한 다음에, 배열을 순회하면서 중간값과 해당 원소의 값의 차이를 더해준 값을 반환하면 된다.

sorting으로는 merge sort를 사용하였고, 이를 코드로 작성하면 아래와 같다.

int temp[100001];

void merge(int* arr, int left, int mid, int right)
{
    int pa, pb, p;

    for(pa=left, pb=mid+1, p=left; pa<=mid && pb<=right; p++)
    {
        if(arr[pa]<=arr[pb]) temp[p] = arr[pa++];
        else temp[p]=arr[pb++];
    }

    while(pa<=mid) temp[p++]=arr[pa++];
    while(pb<=right) temp[p++]=arr[pb++];

    for(p=left;p<=right;p++) arr[p]=temp[p];
}

void merge_sort(int* arr, int left, int right)
{
    if(left<right)
    {
        int mid=left+(right-left)/2;
        merge_sort(arr, left, mid);
        merge_sort(arr, mid+1, right);
        merge(arr, left, mid, right);
    }
}

int minMoves2(int* nums, int numsSize){
    merge_sort(nums, 0, numsSize-1);

    int mid = numsSize/2;
    int answer=0;
    
    for(int i=0;i<numsSize;i++)
    {
        if(i<mid) answer+=(nums[mid]-nums[i]);
        else if(i>mid) answer+=(nums[i]-nums[mid]);
    }

    return answer;
}