[codility] MaxCounters

app.codility.com/programmers/lessons/4-counting_elements/max_counters/

MaxCounters coding task - Learn to Code - Codility

문제에 나온대로 N+1이 됐을 때 마다 n_arr를 새로 만들어줬더니

시간초과 하나가 뜨면서 92퍼 나왔다

최악의 경우 모두 N+1이라면 O(N*M)이라 그런듯

def solution(N, A):
    # write your code in Python 3.6
    n_arr = [0]*N
    n_max = 0
    for i in A:
        if i >=1 and i <=N:
            n_arr[i-1] +=1
            if n_max < n_arr[i-1]:
                n_max = n_arr[i-1]
        elif i == N+1:
            n_arr=[n_max]*N
    return n_arr

 

한번에 하지 말고 변수 하나를 더 써서

고정된 max값보다 A[i]가 크면 1만 더하고

작으면 고정 max값에 1 더한 값으로 지정하도록 한다

마지막에 고정 max보다 적은 값은 보정해준다

O(N+M)으로 끝

def solution(N, A):
    # write your code in Python 3.6
    n_arr = [0]*N
    n_max = 0
    n_max_fixed = 0
    for i in A:
        if i >=1 and i <=N:
            if n_max_fixed < n_arr[i-1]:
                n_arr[i-1] +=1
            else:
                n_arr[i-1] = n_max_fixed + 1

            if n_max < n_arr[i-1]:
                n_max = n_arr[i-1]
        elif i == N+1:
            n_max_fixed = n_max
    for i in range(N):
        if n_arr[i] < n_max_fixed:
            n_arr[i] = n_max_fixed
    return n_arr