Fraudulent Activity Notifications

Sorting관련 알고리즘으로 이 문제를 풀기 위해서는 효율적으로 이진검색을 해야한다.

Problem

HackerLand National Bank has a simple policy for warning clients about possible fraudulent account activity. If the amount spent by a client on a particular day is greater than or equal to $2X$ the client’s median spending for a trailing number of days, they send the client a notification about potential fraud. The bank doesn’t send the client any notifications until they have at least that trailing number of prior days’ transaction data.

Given the number of trailing days $d$ and a client’s total daily expenditures for a period of $n$ days, dtermine the number of times the client will receive a notification over all $n$ days.

앞의 $d$일 동안의 median에 해당하는 값의 두 배 이상의 지출이 현재 발생하였다면 notification을 보내는 것이다. 단순하게 앞에서 sweep하면서 매번 $d$개씩 sorting하게 되면 time complexity가 높아 test를 통과하지 못한다. 문제에서 시간을 줄이기 위해서는 다음 두 단계를 효율적으로 만들어야 한다.

• 이전 $d$일동안의 중간값을 찾기 위한 sorting
• Sweeping을 하면서 새로 숫자가 들어올 때 지울 숫자를 효율적으로 찾기 위한 검색 알고리즘

Answer

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

import bisect

def activityNotifications(expenditure, d):
    notice_cnt = 0
    for i in range(len(expenditure) - d):
        if i == 0:
            window = sorted(expenditure[0:d])
        else:
            del window[bisect.bisect_left(window,expenditure[i-1])]
            bisect.insort(window, expenditure[i+d-1])
        median = window[d//2] if d %2 != 0 else 0.5 * (window[d//2] + window[(d//2)-1])        
        if 2 * median <= expenditure[i + d]:
            notice_cnt += 1
    return notice_cnt

Explanation

앞에서부터 sweeping하는 것은 어쩔 수 없이 해야하는 부분이다. 다만 window 길이는 정해져 있으므로 최초 sweep단계에서 window list를 먼저 설정해주었다. 진행하면서 queue처럼 먼저 들어왔던 element를 내보내야하는데 헷갈리면 안되는 점이 sorting된 window의 첫 번째 element를 빼는 것이 아니라 원래의 expenditure에서 과거 element를 빼야한다는 것이다. 즉 검색이 필요한데 그냥 선형으로 검색하면 $O(n)$인데 이 경우 테스트를 통과하지 못했다. 따라서 보다 빠른 이진탐색트리를 사용해 위치를 검색하는 것으로 바꾸어주었으며 이 경우 $O(\log n)$이 되면서 모든 테스트를 통과할 수 있었다. 삭제를 한 뒤에 새로 들어오는 expenditure를 오름차순으로 넣어주어야 하는데 이 과정에서도 이진탐색을 사용한다. Python에서는 이전탐색이나 sorting을 위한 bisect 모듈이 있으므로 이를 사용하면 편리하다. 먼저 sorting을 해놓고 사용하면 효율적으로 insertion이나 search를 수행할 수 있다. 이후에는 median을 찾아 median의 두 배보다 크거나 같은 경우에 대해 카운트를 올려주면 끝난다.

Reference

• HackerRank