Codility Lesson4 MaxCounter 파이썬 풀이

문제 설명 생략

MaxCounters coding task - Learn to Code - Codility

---

생각보다 시간복잡도 처리에서 오래 걸려서 잘 남기지 않는 ps 포스팅을 남기게 되었다..

 

우선 생각나는 대로 풀어보니 88% 점수를 받았고, largest 케이스에서 시간 초과가 났다.

 

88% 풀이

def solution(N, A):
    answer = [0] * N
    max_counter = N + 1
    maximum = 0

    for num in A:
        if num < max_counter:
            answer[num - 1] += 1
            if answer[num - 1] > maximum:
                maximum = answer[num - 1]
        else:
            answer = [maximum] * N

    return answer

이 풀이는 간단하고 아마 많은 사람들이 첫 번째로 생각하게 되는 풀이라고 생각한다.

그런데 문제점이 있다.

else 구문의 answer = [maximum] * N이다

 

모든 값을 maximum으로 초기화하는 과정에서 리스트의 요소를 N개 만큼 생성한다.

따라서 코딜리티의 추정값은 O(N+M)이지만 N, M의 최대값인 100,000이 값으로 주어지면  O(N^2)의 시간복잡도가 되어버린다.

그래서 마지막 테스트 케이스를 통과할 수가 없다.

---

100% 풀이

def solution(N, A):
    answer = [0]*N
    max_counter = N+1
    cache = 0
    maximum = 0

    for num in A:
        if num < max_counter:
            if answer[num-1] < cache:
                answer[num-1] = cache + 1
            else:
                answer[num-1] += 1

            if answer[num-1] > maximum:
                maximum = answer[num-1]
        else:
            cache = maximum

    for idx in range(N):
        if answer[idx] < cache:
            answer[idx] = cache

    return answer

추가한 아이디어는 최대값을 업데이트하는 것을 똑같이 응용했다.  88% 코드에서도 if num < max_counter인 케이스는 값을 업데이트할 때마다 업데이트한 값이 최대값인지 항상 확인하고 maximum 변수를 업데이트 해주었다. ( max(answer) 같은 방식은 리스트를 순회하기 때문이다. )

 

추가되는 로직은 생각보다 간단하다.

 

1. else 구문) max_counter 값을 만날 때 배열을 초기화하지 않고 cache 변수에 현재까지의 maximum 값을 저장한다.

2. 값을 업데이트할 때, 현재 업데이트 하려고 하는 값이 cache 변수에 저장한 값보다 큰지 작은지 체크한다.

3. 캐시보다 작다면 캐시+1로 업데이트 해준다.

4. 순차 탐색이 끝난 뒤 한 번 더 A배열을 순차탐색 하면서 업데이트 되지 않은 cache보다 작은 값들을  cache 값으로 변경한다.

 

이를 가능하게 하는 것이 else 구문에 있는 cache = maximum 이다.

업데이트를 하게 하는 트리거 라인이다. 

 

max_counter값을 만날 때 배열의 모든 요소를 최대값으로 초기화하는데 이때 배열 자체를 초기화하는 것이 아니라

다음 업데이트에서 업데이트 해야할 값이 cache에 저장한 값보다 큰지, 작은지를 체크해서 반영하는 것이다.

업데이트하려고 하는 값이 만약 cache보다 작다면 최대값으로 초기화하는 로직이 반영되지 않았으므로 cache + 1로 업데이트하고, 그렇지 않다면 아직 최대값으로 초기화해야하는 단계가 아니거나 이미 반영되었으므로 기존값 + 1로 업데이트한다. 

마지막으로 한 번 더 순차탐색을 거치며 cache (최대값)으로 변경되지 않은 요소를 업데이트 한다.