[HackerRank] Sorting - (Medium)Fraudulent Activity Notifications (이상 거래 알림) javascript 문제 풀이

■ 문제

원본 사이트: 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

 

난이도: Medium

최대 스코어: 40

 

● 문제 요약

• 특정 날짜에 고객이 지출한 금액이 이전의 일정 날짜동안 평균적(median 값으로 정함)으로 지출한 금액의 2배 이상이 되면 알림을 보냄
• expenditure: 고객의 지출 내역
• d(trailing days): 평균 지출 금액을 구할 일정 날짜
• 고객이 n일 동안 알림 받을 횟수를 return

※ median(중간값) : 숫자를 오름차순으로 정렬한 뒤, 홀수 개면 가운데에 있는 값으로, 짝수 개면 가운데에 있는 두 값의 평균으로 결정됨

 

예시:

expenditure = [10, 20, 30, 40, 50]
d = 3

• days	trailing expenditures	median	day's expenditures	비고
  1	[]	-	10
  2	[10]	-	20
  3	[10, 20]	-	30
  4	[10, 20, 30]	20	40	---> 알림 전송!
  5	[20, 30, 40]	30	50

• d가 3이기 때문에 3일째까지는 데이터를 계속 모으기만 함
• 4일째부터 알림을 전송할 지 확인
• 4일째에 지출한 금액이 (이전 지출의 median 값)X2와 같기 때문에 알림 전송

==> return 1

 

 

■ 문제 풀이

이 문제는 진짜 풀기 너무 힘들었다...
array.sort를 이용해 매번 정렬을 해서 풀면 타임아웃 오류가 나기 때문에 다른 방법을 이용해야 한다.

여기서의 해답은 계수 정렬(Counting Sorting)을 이용하는 것이다.
계수 정렬이 가끔 나오긴 하지만 제대로 이해하고 있지 않았는데, 이 문제를 풀며 그래도 조금 도움이 된 것 같다.

지출 금액은 0 ~ 200 사이의 정수로만 이루어져있기 때문에 계수 정렬을 사용해 타임 아웃 문제를 해결할 수 있다.
만약 지출 금액의 범위가 높으면 계수 정렬로 해도 문제가 있을 것 같다.

일단, 카운터 배열의 크기는 201이 되고 모두 0으로 초기화를 시켜준다.
그리고 처음 d일 동안 지출한 내역을 토대로 지출 금액을 카운트한다.
위의 예시로 치면 1일에는 counter[10]에 1을 더하고, 2일에는 counter[20]에 1을 더하고 이런 식이 된다.
계수 정렬의 핵심은 해당 값을 인덱스로 설정해 카운트하는 것이다.

데이터들이 다 모이면 알림을 전송할 지 판단한다.
배열은 0부터 시작하기 때문에 i=d부터 끝까지 for문을 돌면 된다.
각 일자마다 median 값을 구하고 해당 날짜의 지출 금액이 median * 2보다 크거나 같으면 알림 횟수를 추가한다.


median 값을 구하는 것도 구현하기 꽤 힘들었다...
일단, 배열이 홀수인지 짝수인지 확인해서 두 개의 로직을 따로 구현했다.

 

● 완성 코드 - 40 Points (Max)

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function(inputStdin) {
    inputString += inputStdin;
});

process.stdin.on('end', function() {
    inputString = inputString.split('\n');

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the 'activityNotifications' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. INTEGER_ARRAY expenditure
 *  2. INTEGER d
 */

function activityNotifications(expenditure, d) {
    // Write your code here
    let notifications = 0;
    let counter = [];
    for(let i=0; i<201; i++){
        counter[i] = 0;
    }
    expenditure.slice(0, d).forEach((v) =>{
        counter[v]++;
    });
    // for(let i=0; i<d; i++){
    //     counter[expenditure[i]]++;
    // }
    
    for(let i=d; i<expenditure.length; i++){
        let median = getMedian(counter, d);
        console.log('median=', median);
        if(expenditure[i] >= median*2){
            notifications++;
        }
        counter[expenditure[i-d]]--;
        counter[expenditure[i]]++;
    }
    
    return notifications;
}

function getMedian(arr, d){
    let median = 0;
    let acc = 0;
    if(d%2 === 0){
        let first = 0;
        let second = 0;
        for(let i=0; i<arr.length; i++){
            acc += arr[i];
            if(first === 0 && acc >= d/2){
                first = i;
            }
            if(second === 0 && acc >= d/2 + 1){
                second = i;
                break;
            }
        }
        median = (first + second) / 2;
    }
    else{
        for(let i=0; i<arr.length; i++){
            acc += arr[i];
            if(acc > d/2){
                median = i;
                break;
            }
        }
    }
    return median;
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const firstMultipleInput = readLine().replace(/\s+$/g, '').split(' ');

    const n = parseInt(firstMultipleInput[0], 10);

    const d = parseInt(firstMultipleInput[1], 10);

    const expenditure = readLine().replace(/\s+$/g, '').split(' ').map(expenditureTemp => parseInt(expenditureTemp, 10));

    const result = activityNotifications(expenditure, d);

    ws.write(result + '\n');

    ws.end();
}

 

 

■ 결론

이 문제의 핵심은 계수 정렬인데 계수 정렬을 제대로 알지 못해서 엄청 많이 헤맸다.

다음에 계수 정렬에 대해 정리해서 다시 올려야겠다.