codility - MaxCounters

문제

• 주어진 배열을 기반으로 최종적으로 만들어지는 counters 반환
• 이때 배열의 원소을 통해 operation을 선택

내 코드

def solution(N, A):
    counters = [0] * N
    for x in A:
        if x >= 1 and x<=N:
            counters[x-1] += 1
        elif x == N+1:
            counters = [max(counters)] * N
    return counters

• N, M은 최대 100,000까지 가능
• max 값을 구할 때 O(N)이 걸림: 모든 요소를 다 훓어봐야하니까.
• 하지만 매번, 즉 M개의 요소 모두가 최댓값을 찾는 연산으로만 구성되어 있으면 O(NxM) 이 됨

지피티 코드

def solution(N, A):
    counters = [0] * N
    max_val = 0
    base_val = 0

    for x in A:
        if 1 <= x <= N:
            if counters[x - 1] < base_val:
                counters[x - 1] = base_val
            counters[x - 1] += 1
            max_val = max(max_val, counters[x - 1])
        else:
            base_val = max_val

    for i in range(N):
        if counters[i] < base_val:
            counters[i] = base_val

    return counters

• max counter를 할 때 바로 업데이트를 하지 않음
• 즉, 필요할 때만 갱신
• 어짜피 초기화가 0으로 된다는 점 이용
• 내가 푸는 문제의 요소들의 최댓값까지 꼭 고려하자