Fraudulent Activity Notifications

def get_median(counter, d):
    count = 0
    for i, c in enumerate(counter):
        count += c
        if count > d // 2:
            # 여기서 찾은 i 값이 중앙값(d=홀수 일 경우)
            break
    
    if d % 2 == 1:
        return i * 2    
    else:
        for j in range(i, -1, -1):
            # 전 인덱스부터 검사하는게 아니라 현재 인덱스부터 검사한다.
            # 카운팅 한 개수이기 때문에 같은 수 일 수 있다.
            count -= counter[j]
            if count < d//2:
                break

        return i + j
            
def activityNotifications(expenditure, d):
    count = 0
    counter = [0]*201
    for exp in expenditure[:d]:
        counter[exp] += 1
    
    # [0, 1, 1, 1]
    # 1 2 3 4 4 3, d=4
    for i in range(d, len(expenditure)):
        tail = expenditure[i]
        head = expenditure[i-d]

        median = get_median(counter, d)
        if tail >= median:
            count += 1
        
        counter[tail] += 1
        counter[head] -= 1

    return count

 

이 문제는 너무 어려웠다. 중앙값을 구하려면 무조건 정렬을 해야했기 때문에 정렬을 아무리 최적화 한다고 해도 시간 복잡도 를 만족 시킬 수 없었다.

 

그럼 문제는 매 순회 때마다 정렬하는게 아니라는 건데… 그래서 처음에는 힙 을 이용해서 접근 했었다. 최대힙과 최소힙을 이용하면 중앙 값 을 바로 구할 수 있는 방법이 있는데… 이건 전체의 자료에 대한 중앙 값 이라서 이 문제와 맞지 않았다. 그러다 계수 정렬 이란게 존재하는 걸 알았다. 제한된 범위에서는 O(n)의 시간 복잡도를 나타내는 정렬이다. 비 비교 정렬 알고리즘이다.

비 비교 정렬 알고리즘: 계수정렬, 기수정렬

 

계수 정렬은 각 숫자의 카운팅을 메모리에 저장해서 정렬하는 방식이다. 카운팅을 했을 때 이미 정렬이 되어있는 인덱스를 얻을 수 있다. 그래서 주어진 d에 대해서 중앙값의 인덱스를 찾고자 하면 카운팅 배열의 누적 합 이 중앙값의 인덱스보다 클 경우이다.

카운팅 배열의 값은 각 숫자의 카운팅이기 때문에 누적합은 현재 정렬된 배열의 상태를 나타내기 때문이다. 누적합을 알면 중앙 값이 무엇인지가 바로 나온다.

 

그렇게 나온 값을 짝수 일 경우만 조심해서 처리해주면 문제를 풀 수 있다.