문제 링크

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

주의사항

문제 풀이

• 시간초과

from statistics import median

def activityNotifications(expenditure, d):
    # Write your code here
    cnt = 0
    for i in range(d, len(expenditure)):
        today = expenditure[i]
        m = median(expenditure[i-d:i])
        check = False
        if expenditure[i] >= 2*m:
            cnt += 1
    return cnt

• 계수정렬

def getMedian(cnt_arr, d):
    total_cnt = 0
    for i in range(len(cnt_arr)):
        total_cnt += cnt_arr[i]
        if d % 2:
            if total_cnt >= d // 2 + 1:
                return i
        else:
            if total_cnt == d // 2:
                for j in range(i+1, len(cnt_arr)):
                    if cnt_arr[j] > 0:
                        return (i+j)/2
            elif total_cnt > d // 2:
                return i        

def activityNotifications(expenditure, d):
    # Write your code here
    answer = 0
    cnt_arr = [0]*201 # 각 숫자의 개수를 넣기 위한 array
    
    for i in range(d):
        cnt_arr[expenditure[i]] += 1 # d개 까지는 개수만 확인하기
    
    for i in range(d, len(expenditure)):
        if expenditure[i] >= 2*getMedian(cnt_arr, d):
            answer += 1
        cnt_arr[expenditure[i-d]] -= 1
        cnt_arr[expenditure[i]] += 1
    return answer

• bisect 활용

from bisect import bisect_left, insort
def activityNotifications(expenditure, d):
    # Write your code here
    cnt = 0
    mid1 = d // 2
    mid2 = d // 2 if d % 2 else d // 2 - 1
    
    sorted_exp = 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_left(sorted_exp, x)
            sorted_exp.pop(idx)
            insort(sorted_exp, expenditure[i])
        
        if exp >= sorted_exp[mid1] + sorted_exp[mid2]:
            cnt += 1
    return cnt