[Hackerrank] [Medium] Fraudulent Activity Notifications

https://www.hackerrank.com/challenges/fraudulent-activity-notifications/problem

Fraudulent Activity Notifications | HackerRank

풀이

• d길이를 유지하면서 median을 유동적으로 계속 구해줘야함.
• 한 번 iteration할 때마다 sort하고, median을 직접 계산하면 timeout.
• 문제 조건에서 expenditure[i]는 0 이상 200 이하의 정수임을 명시했기 때문에 이를 count하는 배열을 만들어 median을 구하는데 활용.
  • count[expenditure[i]] = frequency
  • expenditure[i]의 빈도 수를 저장하는 리스트 만듬.
• d가 홀수일 때, 짝수일 때 median을 구하는 방법이 다름.
  • 리스트가 주어졌을 때,
  • 홀수일 때 : 가운데 index의 값을 반환 ; [a1, a2, a3, a4, a5] -> a3
  • 짝수일 때 : 가운데 두 수의 평균을 반환 ; [a1, a2, a3, a4] -> (a2 + a3) / 2
• count의 index가 expenditure[i]이기 때문에, 처음 d개로 median을 구하고, 매번 count[expenditure[i - d] ]의 값을 1 감소시킴으로써 median을 구할 때 element개수를 d개로 유지하기 쉬움.

def activityNotifications(expenditure, d):
    def get_median(count, d):
        counting = 0

        if d % 2 == 0:
            mid_1, mid_2 = 0, 0
            for idx, freq in enumerate(count):
                counting += freq
                if mid_1 == 0 and counting >= (d//2):
                    mid_1 = idx
                if mid_2 == 0 and counting >= (d//2 +1):
                    mid_2 = idx
                    return (mid_1+mid_2) / 2
        else:
            for idx, freq in enumerate(count):
                counting += freq
                if counting >= (d // 2) + 1:
                    return idx

    ans = 0
    count = [0]*200
    for idx, spend in enumerate(expenditure):
        if idx < d: 
            count[spend] += 1
            continue
        median = get_median(count, d)

        if spend >= 2 * median:
            ans += 1

        # 현재 spend를 count에 추가하고, d 이전의 spend를 count에서 제외시킴
        count[spend] += 1
        count[expenditure[idx-d]] -= 1

    return ans