[코딜리티] 파이썬 _ MaxCounters

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

MaxCounters coding task - Learn to Code - Codility

 

문제풀이 : 

• 이문제는 시간초과가 빡세다
• 구현은 엄청 쉬운데 그냥 일반적이게 구현하면 시간초과가 나는데 해결하기위한 아이디어는 max counter가 마지막으로 일어나는 시점을 통해 해결해야한다.
• 마지막 max counter 작업이 수행되면 지금까지의 최대로 어차피 모든것이 갱신되므로 그 값만 저장해놓으면 그 이전에 발생하는 max_counter에 대해서는 생각하지 않아도 되기때문이다. ( 전체를 다 갱신하고 다시 작업하고 이런 과정을 생략할 수 있다.)
• 말로 설명하는것보다 코드를 보면 더 이해가 잘 갈것이다.

추가로 counters를 그냥 배열로 만들면 시간초과가 여전히 나는데 딕셔너리로 해서 증가된 값만 확인하도록 하면 시간초과가 해결된다.

배열을 돌면서 0인건 continue를 해도 시간초과가 나기때문에 배열로는 안되는것같다.

 

 

정답코드 : 

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
from collections import defaultdict
def solution(N, A):
    # write your code in Python 3.6
    
    counters = defaultdict(int)
    max_val = 0
    cnt = 0

    for i in range(len(A)):
        if A[i] <= N:
            counters[A[i]] += 1
            max_val = max(max_val, counters[A[i]])
        else:
            cnt += max_val
            max_val = 0
            counters.clear()
    
    answer = [cnt] * N
    # print(answer)
    # print(counters)

    for key, val in counters.items():
        answer[key-1] += val

    return answer