알고리즘 스터디 - HackerRank : Fraudulent Activity Notifications

문제 해석

• N일 동안 사용한 은행 지출 기록이 존재하고 있을 때 잘못된 거래를 감지하는 것이 목적이다.
• 예를 들어, expenditure = [10, 20, 30, 40, 50], d = 3일 때 3일 째 되는 날의 중앙값은 20으로 다음 사용 값이 40이므로 40 >= 2x20으로 은행에 알림이 가게 된다.
• 여기서 지출의 중앙값을 구하고 다음날 값 >= 2x중앙값이면 전체 알림 횟수가 증가한다.

알고리즘을 어떻게 사용해야할까?

1. D만큼의 배열을 자른다.(배열을 0 <= i <= n-1-d 기준 안에서 돌린다.)
2. set()로 고유값을 만든다.
3. sort로 정렬해 중앙값을 찾는다.
4. 알림 조건이 만족되는지 끝날 때까지 찾아본다.
5. 최종 알림 횟수를 출력한다.

• 위 방법을 사용해봤는데 시간초과가 발생하게 되었다. 그래서 다른 사람들이 한 코드를 살펴보게 되었는데 Bisect를 이용해 이분 탐색을 하는 방식이었다.

알고리즘 코드

#!/bin/python3

import math
import os
import random
import re
import sys
import bisect

#
# 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
#

def activityNotifications(expenditure, d):
    # Write your code here
    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

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    first_multiple_input = input().rstrip().split()

    n = int(first_multiple_input[0])

    d = int(first_multiple_input[1])

    expenditure = list(map(int, input().rstrip().split()))

    result = activityNotifications(expenditure, d)

    fptr.write(str(result) + '\n')

    fptr.close()