Fraudulent Activity Notifications

사이트: HackerRank
난이도: 미디움
분류: Sorting

문제

일자에 따라 지출 값의 배열이 주어지고 지정된 일자가 지난 후, 다음날 지출 금액이 지정된 일자동안 지출한 금액의 중앙값 * 2 보다 클 경우 보안 경고 알람을 사용자에게 보낸다. 문제에서는 보안 경고 알람이 몇번 울렸는지 카운팅해서 반환하라고 한다.

// 일자에 따른 지출 금액 목록
expenditure = [10, 20, 30, 40, 50]
// 중앙 값을 산출하기 위한 지정된 일자
d = 3

위 값을 가지고 중앙값을 산출해 보면 아래와 같다.

	지출 금액 목록	중앙값	지출 금액	알림 기준 금액	알림
1일차	[10, 20, 30]	20	40	20 * 2 = 40	전송
2일차	[20, 30, 40]	30	50	30 * 2 = 60	없음

따라서 위 예시의 답은 1이다.

1. 나의 풀이

처음 문제를 접했을 때, 주어진 배열 expenditure에서 파생 배열의 min, max만 잘 관리하면 되겠는데? 라는 생각을 했었다. 그래서 떠오른 자료구조가 min heap이었는데, 막상 로직을 모두 작성하고 보니까 시간 복잡도 효율이 좋지 않은 구조로 작성되어서 애를 많이 먹었다.
아래 로직은 올바른 답을 산출하지만, 시간 복잡도를 너무 잡아먹어서 결국 모든 테스트 케이스를 통과하지 못했다.

function activityNotifications(expenditure, d) {
    // Write your code here
    const heap = new MinHeap();
    let count = 0;
    
    for (let i = 0; i < expenditure.length; i++) {
        if (i >= d) {
            const min = heap.min();
            const max = heap.max();
            const median = min + ((max - min) / 2);

            if (expenditure[i] >= (median * 2)) {
                count++;
            }
            
            heap.pop(expenditure[i - d]);
        }
        
        heap.push(expenditure[i]);
    }
    
    return count;
}

class MinHeap {
    constructor() {
        this.heap = [null];
    }
    
    push(value) {
        this.heap.push(value);
        let current = this.heap.length - 1;
        let parent = Math.floor(current / 2);

        while(parent !== 0 && this.heap[parent] > value) {
            this.swap(current, parent);
            current = parent;
            parent = Math.floor(current / 2);
        }
    }
    
    pop(value) {
        let current = 1;
        if (value !== undefined) {
            current = this.heap.findIndex(v => v === value);
            
            if (current === -1) {
                return;
            }
        }

        const result = this.heap[current];
        this.heap[current] = this.heap.pop();

        let left = current * 2;
        let right = (current * 2) + 1;
        
        while(
            this.heap[current] > this.heap[left] ||
            this.heap[current] > this.heap[right]
        ) {
            if (this.heap[left] > this.heap[right]) {
                this.swap(current, right);
                current = right;
            } else if (this.heap[current] > this.heap[left]) {
                this.swap(current, left);
                current = left;
            }
            
            left = current * 2;
            right = (current * 2) + 1;
        }
        
        return result;
    }
    
    swap(a, b) {
        [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
    }
    
    min() {
        return this.heap[1];
    }
    
    max() {
        return this.heap.reduce((max, v) => max < v ? v : max, 0);
    }
}

2. 다른사람의 풀이

조금 찾아보니까 해당 문제는 계수정렬(counting sort)을 가지고 푸는 문제였다. 계수정렬의 개념을 정확히 몰라서 해당 문제를 잘못 접근해서 풀었던 것이다.

계수정렬의 개념을 다시 짚고 싶다면 링크된 포스트를 확인해보자.

function activityNotifications(expenditure, d) {
  	// 문제에서는 1 ~ 200 까지의 범위라고 명시되어 있으므로 
  	// 200개의 counting 요소들을 0으로 초기화한다.
  	// 1부터 시작이므로 길이값이 201인 배열로 생성한다.
    const counter = new Array(201).fill(0);
  	let notifications = 0;

    expenditure.slice(0, d)
      .forEach((v) => counter[v]++);
    
    for (let i = d; i < expenditure.length; i++) {
      	// 중앙값을 계산하여 가져온다.
        const median = getMedian(counter, d);

      	// 현재 지출 금액이 중앙값 보다 클 경우 알람을 울린다.
        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;
}