[Hackerrank in C] fraudulent activity notifications

문제

https://www.hackerrank.com/challenges/fraudulent-activity-notifications/problem?isFullScreen=true&h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=sorting

Fraudulent Activity Notifications | HackerRank

 

풀이

median 을 구하는 방법을 파악하는게 이 문제의 메인이다.

 

처음(코드1)에는 d개의 숫자를 sort해서 가운데의 2개의 숫자의 합이나 1개의 숫자 * 2로 median*2를 구했다.

이 경우, qsort 가 dlog(d) 씩 n-d 번 반복되므로  dlog(d) * (n-d) = O(nlogd) 걸리게 된다. - 상당히 김.

 

그러므로 다르게 median을 구해야한다.

 

median 은 d개의 숫자배열의 가운데 숫자이므로, d개의 숫자들의 frequency를 찾고, freq_sum 이 d/2될때의 숫자를 구하면 된다.

코드를 보면 훨씬 이해가 잘된다.. (코드2)

sliding window와 같은 방법으로 freq array를 업데이트 시킨다.

 

코드1 (time limit exceeded with qsort)

int cmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int median(int* expenditure, int d, int a, int b){
    int arr[d];
    int idx = 0;
    
    for(int i=a; i<=b; i++) {
        arr[idx++] = expenditure[i];
    }
    
    qsort(arr, d, sizeof(int), cmp);
    
    if(d%2 == 0) return (arr[d/2-1]+arr[d/2]);
    return arr[d/2] * 2;
}
int activityNotifications(int expenditure_count, int* expenditure, int d) {
    int noti = 0;
    
    for(int i=d;i<expenditure_count; i++) {
        if(median(expenditure, d, i-d, i-1) <= expenditure[i]) noti++;
        printf("expenditure: %d, noti: %d, median:  %d\n", expenditure[i], noti,median(expenditure, d, i-d, i-1));
    }
    return noti;
}

 

코드2 (passed)

int getMedian(int* freq, int d) {
    int count = 0;
    if(d%2 == 0) { // even
        int first = -1, second = -1; // two medians
        
        for(int i=0; i<=200; i++) {
            count += freq[i];
            if(first == -1 && count >= d/2) first = i;
            if(second == -1 && count >= d/2 +1) {
                second = i;
                break;
            }
        }
        return first + second;
    } else { // odd
        for(int i=0; i<=200; i++) {
            count += freq[i];
            if(count >= (d+1)/2) return i*2;
        }
    }
    return 0;
}
int activityNotifications(int expenditure_count, int* expenditure, int d) {
    int noti = 0;
    int freq[201] = {0}; // max expenditure
    
    for(int i=0; i<d; i++) {
        freq[expenditure[i]]++;
    }
    
    for(int i=d;i<expenditure_count; i++) {
        if(getMedian(freq, d) <= expenditure[i]) noti++;
        
        freq[expenditure[i-d]]--;
        freq[expenditure[i]]++;
    }
    return noti;
}