[Codility] MaxCounters

77%

효율성 - 2 :: counters array를 초기화하는 것도 시간이 걸림

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

    for a in A:
        if a > N:
            counters = [m]*N
        else:
            counters[a-1] += 1
            m=max(counters[a-1], m)
    
    if isNup :
        for i, c in enumerate(counters):
            if c < curMax:
                counters[i] = curMax
    return counters

100%

counters array 초기화를 최소화!

• current Max value 값을 update
• 반복문(A look up) 진행중에 current Max value 값보다 작은 값이 있으면 current Max value로 바꾸고 increase +1
• 반복문이 끝난 후 counters를 모두 보며 current Max value 보다 작은 값을 한꺼번에 업데이트 해줌 :: current Max value는 계속 업데이트되는데 A look up 반복문에서 이미 지나간 값에 대해 업데이트를 해주지 않기 때문에 마지막에 한꺼번에 업데이트 해주게되면 time complexity를 줄일 수 있다.

def solution(N, A):
    counters = [0] * N
    isNup = False
    m = 0
    curMax = 0

    for a in A:
        if a > N:
            isNup = True
            curMax = m
        else:
            if counters[a-1] < curMax :
                counters[a-1] = curMax
            counters[a-1] += 1
            m=max(counters[a-1], m)
    
    if isNup :
        for i, c in enumerate(counters):
            if c < curMax:
                counters[i] = curMax
    return counters