[Codility] Lesson4. Max Counters (Python)

1. 문제

app.codility.com/c/run/trainingNPTET7-BCU/

Codility

2. 풀이

Time out 이 났었던 문제.

max값은 리스트의 값을 갱신할때마다 함께 갱신해주고

A[K] = N+1일 경우 max_val을 갱신해 준다.

li[A[K]-1]의 값을 증가 counter + 1 할 때에는 해당 리스트의 값이 max_val 보다 작으면 max_val로 맞춰주면서 조정하고

그 후에 +1을 해준다.

 

시간복잡도를 생각하면서 풀어햐했던 문제.

 

3. 코드

def solution(N, A):
    li = [0 for _ in range(N)]
    max_val = 0
    cur = 0

    for i in range(len(A)):
        if A[i] == N+1:
            max_val = cur
        else:
            if li[A[i]-1] < max_val:  #현재 값이 max보다 작으면 max값으로 조정
                li[A[i]-1] = max_val
            li[A[i]-1] += 1
            if cur < li[A[i]-1]:  #max값 갱신
                cur = li[A[i]-1]

    for i in range(N):
        if li[i] < max_val:
            li[i] = max_val

    return li