codility: MaxCounters 파이썬

코딜리티는 발암이다...

시간 초과가 여기서 났다..

나 울어ㅠ

 

 

알아서 엣지 포인트를 생각해야하는데 쉽지 않다. 시간 초과가 계속 나는데 진짜 창의적으로 돌아갔다. 다시 여기다.

테케 통과했다고 바로 submit 안하는 습관을 늘려야한다. 히든 케이스는 반드시 존재한다.

하다 안돼서 답봤다.

def solution(N,A):
	li = {i:0 for i in range(1, N+1)}
    max_sum = 0
    max_num = 0
    for key in A:
    	if key ==N+1:
        	max_sum +=max_num
            li.clear() 
            max_num = 0
        else:
        	if li.get(key)  is None:
            	li[key]=1
            else:
            	li[key]+=1
            max_num = max(max_num, li[key])
     answer = [max_sum]*N
     for key, val in li.items():
     	answer[key-1] +=val
     return answer

참고링크: choichumji.tistory.com/89

 

 

 

 

 

우선 88점짜리 내 코드

O(n+m) 의 복잡도를 가진 이친구는  슬프다..

def solution(N, A):
    ground=0
    counters =[ground]*N
    max_counters=0
    for i in A:
        i-=1
        if i<N:
            counters[i]+=1
            max_counters=max(max_counters,   counters[i] )
        else:
            counters =[max_counters]*N# 이게 발암의 근원 돌아버리겠음
            
    
    return counters

짜증나기 직전

def solution(N, A):
    ground=0
    basic =  [0]*N
    
    counters =basic[:]
    
    max_counters=0
    for i in A:
        i-=1
        if i<N:
            counters[i]+=1
            max_counters=max(max_counters,   counters[i] )
        else:
            ground+=max_counters
            counters = basic[:] #[max_counters]*N# 이게 발암의 근원 돌아버리겠음max_counters,
            max_counters=0
            
    return list(map(lambda a: a+ground, counters)) 
solution(11, [3,12,4,10,10,6])