[HackerRank] Fraudulent Activity Notifications #이진탐색 #이분탐색 #바이너리서치 #bisect #sort

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

Fraudulent Activity Notifications | HackerRank

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, determine the number of times the client will receive a notification over all n days.

풀이

expenditure 리스트에서 [-d일 ~ -1일]을 정렬하여 중앙값을 찾아냅니다. 2 * 중앙값보다 현재 값이 더 크거나 같으면 count += 1. count를 반환합니다.

문제는 시간 초과입니다. 정렬을 매번 수행할 때의 시간복잡도는 O(len(expenditure) * d log d)입니다. 또한, 요소의 값이 모두 바뀌는 게 아니기 때문에 불필요하게 정렬하는 감도 있습니다. 인덱스가 가장 작은 값을 제거하고, 새로운 인덱스의 값을 정렬되게 삽입하면 오버헤드를 줄일 수 있습니다.

물론 이 때에도 값을 순차적으로 비교하여 삽입하면 시간 초과가 발생합니다. 순차 비교의 시간복잡도는 O(n), O(n)보다 작은 시간복잡도로는 O(log n)이 있으며, 이진탐색이 바로 O(log n)의 시간복잡도를 갖는 알고리즘입니다. 값을 제거하고 삽입할 때 이진탐색을 사용해봅시다.

중앙값의 인덱스를 미리 계산해놓아 오버헤드를 줄였으며, 제거되는 값과 새로 들어오는 값이 같은 경우에는 제거, 삽입을 실행하지 않도록 하여 오버헤드를 줄였습니다.

def activityNotifications(expenditure, d):
    count = 0
    mid1 = d // 2
    mid2 = mid1 if d % 2 else mid1 - 1
 
    subexp = sorted(expenditure[:d])
    for i, exp in enumerate(expenditure[d:], d-1):
        x = expenditure[i-d]
        if i != d-1 and x != expenditure[i]:
            idx = bisect.bisect_left(subexp, x)
            subexp.pop(idx)
            bisect.insort(subexp, expenditure[i])

        if exp >= subexp[mid1] + subexp[mid2]:
            count += 1
    return count

파이썬에는 이진탐색과 이진탐색 이후 삽입을 돕는 라이브러리 bisect가 있습니다. bisect_left는 array에 x 값이 삽입될 지점을 찾는 함수이지만, 다음과 같은 조건이 만족된다면 주어진 값의 인덱스를 찾는데에도 사용할 수 있습니다. (우리는 존재하는 값을 찾는 것이기 때문에 다음과 같은 조건식이 없어도 무조건 만족합니다. 생략.)

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

https://docs.python.org/3/library/bisect.html

bisect — Array bisection algorithm — Python 3.9.5 documentation