Intuition

$argmin_x\sum\left\vert arr_i-x \right\vert$을 찾는 문제로 귀결된다.
이때 $x$는 중간의 적당한 어떤 값인 평균이나 중앙값 중 하나일 것이라고 추측했다.

Approach

중앙값일 때 결과값이 최소화되고 중앙값에서 멀어질수록 결과값이 커지는 패턴을 발견할 수 있다.

중앙값을 찾기 위해 배열을 정렬한다음 문제를 풀이해주면 된다.

Solution

#include <stdlib.h>
#define ABS(x) (x)<0?-(x):(x)

void merge(int* nums, int l, int r, int mid){
    int i=l;
    int j=mid+1;

    int* tmp=(int*)malloc(sizeof(int)*100000);
    int tmpP=l;

    while(i<=mid&&j<=r){
        if (nums[i]>nums[j]) tmp[tmpP++]=nums[j++];
        else tmp[tmpP++]=nums[i++]; 
    }

    while(i<=mid) tmp[tmpP++]=nums[i++];
    while(j<=r) tmp[tmpP++]=nums[j++];

    for (int k=l;k<=r;k++) nums[k]=tmp[k];
    free(tmp);
}

void split(int* nums, int l, int r){
    if (l<r){
        int mid=l+(r-l)/2;
        split(nums,l,mid);
        split(nums,mid+1,r);
        merge(nums,l,r,mid);
    }
}

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

    int median;

    if (numsSize%2) median=nums[numsSize/2]; // odd
    else median=(nums[numsSize/2]+nums[numsSize/2-1])/2; // even

    int res=0;
    for (int i=0;i<numsSize;i++) res+=ABS(median-nums[i]);
    return res;
}

Time Complexity

MergeSort를 사용했기때문에 $O(NlogN)$이 소요된다.

Sorting

MergeSort말고 QuickSort나 HeapSort를 사용해도 무관하다.
아래에는 퀵소트와 힙소트를 작성해보았다.

#include<stdio.h>

void swap(int* arr, int a, int b){
    int tmp=arr[a];
    arr[a]=arr[b];
    arr[b]=tmp;
}

int partition(int* arr, int left, int right){
    int low=left+1;
    int high=right;
    
    while(1){ 
        while(low<right&&arr[low]<=arr[left]) low++;
        while(high>left&&arr[high]>=arr[left]) high--;

        if (high<=low){
            swap(arr,left,high);
            return high;
        }
        swap(arr,low,high);
    }
}

void quickSort(int* arr, int left, int right){
    if (left<right){
        int pivotIdx=partition(arr,left,right);
        quickSort(arr,left,pivotIdx-1);
        quickSort(arr,pivotIdx+1,right);
    }
}

int main(void) {
    int arr[]={6,1,2,4,5,9,100,-1,5,23,6,346,234,8,23,92,53,23,5,42,723,96,29,12,79,2,7,-2,64,2};
    quickSort(arr,0,sizeof(arr)/sizeof(int)-1);
    for(int i=0;i<sizeof(arr)/sizeof(int);i++) printf("%d ",arr[i]);
    return 0;
}

#include <stdio.h>

int heap[100];
int heapSize=0;

void insertionHeap(int ele){
    heapSize++;
    int cur=heapSize;
    while(cur>1&&ele>heap[cur/2]){
        heap[cur]=heap[cur/2];
        cur/=2;
    }
    heap[cur]=ele;
}

int getChild(int cur){
    return heap[cur*2]<heap[cur*2+1]?(cur*2+1):(cur*2);
}

int deletionHeap(){
    int ele=heap[heapSize--];
    int ret=heap[1];
    int cur=1;
    int child;
    
    while(cur*2<=heapSize&&ele<heap[(child=getChild(cur))]){
        heap[cur]=heap[child];
        cur=child;
    }
    heap[cur]=ele;
    
    return ret;
}

int main(){
    int arr[]={9,-3,643,23,7,4,9,0,1,52,-346,735,235,26,1,7,374,17,-3,-92,-1,-8,27,32,97,1,-2,60,8,12};
    for (int i=0;i<sizeof(arr)/sizeof(int);i++) insertionHeap(arr[i]);
    for (int i=0;i<sizeof(arr)/sizeof(int);i++) printf("%d ",deletionHeap());
    printf("\n");
}

지적 및 질문 환영