[algorithm] Fraudulent Activity Notifications (Hackerrank) - 답있음 주의

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

Fraudulent Activity Notifications | HackerRank

 

 

첫번째. 중간값을 구합니다.
    짝수의 경우, 중간에 있는 두 수의 평균을 중간값으로 합니다.
    홀수의 경우, 중간에 있는 값을 중간값으로 합니다.

두번째. 그 중간 값에 2를 곱한 후 그보다 크거나 같은 값들의 개수를 반환합니다.

저는 처음에 이 문제를 풀 때 c++ stl인 sort를 이용하여 풀었더니,

시간초과 오류가 났습니다.

그도 그럴 것이, 이 문제에서는 이중 for문이 돌아가게 되면

10^5 * 10^5 = 10^10 로 시간 초과가 날 수 밖에 없습니다.

 

결국 검색을 해볼 수 밖에 없었는데 저는 count sort라는 것을 처음 알게 되었습니다.

https://bowbowbow.tistory.com/8

Counting Sort : 계수 정렬

이 블로그가 큰 도움이 되었습니다.

 

코드는 이렇습니다.

double getMedian(int trdatas[],int d){
    int count = 0;
    double median;
    
    if(d % 2 != 0){
        for(int i = 0; i <= 200; i++){
            count += trdatas[i];
            if(count > d / 2){
                median = i;
                break;
            }
        }
    }
    else{
        int firstData = 0,secondData = 0;
        for(int i = 0; i <= 200; i++){
            count += trdatas[i];
            if(firstData == 0 && count >= d / 2)
                firstData = i;
            if(secondData == 0 && count >= d / 2 + 1){
                secondData = i;
                break;
            }
        }
        median = (firstData + secondData) / 2.0;
    }
    
    return median;
}

// Complete the activityNotifications function below.
int activityNotifications(vector<int> expenditure, int d) {
    int trdatas[201] = {0},answer = 0;
    for(int i = 0; i < d; i++)
        trdatas[expenditure[i]]++;
    for(int i = d; i < expenditure.size(); i++){
        double median = getMedian(trdatas,d);
        cout << median << "\n";
        if(median *2 <= expenditure[i])
            answer++;
        trdatas[expenditure[i - d]]--;
        trdatas[expenditure[i]]++;
    }
    return answer;
}