Codility - MaxCounters

시간 복잡도: O(N*M) --> 66%의 정답률

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(N, A):
    # write your code in Python 3.6
    
    # step 1 - make a arr, consist of int '0', length is N
    tmp = [0]*N
    
    # do the job along case
    for i in A:
        if i <= N and i >= 1:
            tmp[i-1] += 1
            continue
        if i == N + 1:
            tmp = [max(tmp)]*N
    
    
    return tmp
        
            
    pass

시간 복잡도: O(N*M) --> 66%의 정답률

 

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(N, A):
    # write your code in Python 3.6
    
    # step 1 - input N,A
    # already succeed
    
    # step 2 - get for setence
    tmp = [0]*N
    
    for i in A:
        try:
            tmp[i-1] += 1
        except:
            tmp = [max(tmp)]*N
    return tmp
    
    
    pass

 

다른 사람의 코드 : 시간 복잡도: O(N+M) --> 100%의 정답률

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(N, A):
    # write your code in Python 3.6
    
    # step 1 - input N,A
    # already succeed
    
    # step 2 - get for setence
    counters = N * [0]
    next_max_counter =  max_counter = 0
    
    for oper in A:
        try:
            current_counter = counters[oper-1] = max(counters[oper-1] +1, max_counter+1)
            next_max_counter = max(current_counter, next_max_counter)
        except:
            max_counter = next_max_counter
    
    
    return [c if c > max_counter else max_counter for c in counters]
    
    
    pass