[ Codility 코딜리티 ] Lesson 4 MaxCounters Python 파이썬 풀이

 

// 문제 요약

 

N개의 0으로 초기화되어있는

카운터가 주어진다.

이때 카운터에 할 수 있는 연산은

increase(X) : X번째 항에 1을 더한다

max counter : 카운터의 모든 항을 카운터의 현재 최대값으로 바꾼다.

이 두가지 뿐이다.

 

M개의 정수로 구성되어 있고

비어있지 않은 배열 A가 주어지면

아래와 같은 연산을 수행한다.

A[K] = X 인 경우 X가 1에서 N사이 일때 increas(X),

A[K] = N+1 일때는 max counter.

 

위의 연산들이 주어졌을때

N과 A가 주어지면

최종적으로 얻어지는 카운터를 return하는

함수를 만들어라

 

 

// 문제 풀이

 

슬슬 문제들이 복잡하고 난해해지기 시작한다.

그래도 잘 한번 따라가 보자.

 

이런 류의 문제들은

기믹을 빨리 파악하는 것이 중요하다.

즉 모든 원소를 다 들여다보고

일일이 결정을 해야할 일 같지만

사실은 max counter의 성질에 의해

N+1이 언제 몇번 나타났는지만 생각하면

간단해지는 문제라고 할 수 있다.

 

특히나

[파이썬 알고리즘 인터뷰 (책만 출판, 박상길 저)] 에서는

동일한 기능이라면

파이썬의 인터프리터로 구동되는 루프보다

CPython과 같은 컴파일러 단에서

실행되도록 짜여진 루프가

훨씬 빠르다는 것을 말하고 있다.

 

따라서 collections.Counter()를 사용하여

필요할때만 max value를 구하는 방식으로

문제를 풀 수 있겠다.

 

 

코드를 먼저 보자.

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

def solution(N, A):
    # write your code in Python 3.6
    max_count = 0
    p_left = p_right = -1
    for i, n in enumerate(A):
        # max_count
        if n > N:
            p_left, p_right = p_right + 1, i

            # if first max_count is not the first element
            if A[p_left: p_right]:
                increase = collections.Counter(A[p_left: p_right])
                max_count += max(increase.values())

    if len(A) == p_right:
        return [max_count] * N
    else:
        count = [max_count] * N
        increase = collections.Counter(A[p_right + 1:])
        for key, val in increase.items():
            count[key - 1] += val
        return count

우선은 max_count라는 정수를 도입한다.

 

만약 counter의 길이가 엄청나게 길어지면

A를 조회하는 for문 안에서

counter를 연산하는 for문이 돌아야하므로

O(N*M)의 복잡도가 될 것을 예상할 수 있다.

 

반면 max count 연산의 특징을 고려해

이를 정수형으로 찾기만 하면

O(M)의 연산이 O(1)이 되므로

시간복잡도를 줄일 수 있다.

 

결국 마지막에는

O(M)의 루프를 한번 돌려야하므로

이 문제는 O(N+M)의 복잡도 까지 낮출 수 있다.

 

 

풀이에는 2개의 파티션을 이용해서 풀이하였는데

위와같이 옮겨가면서

파티션 사이의 max값만을 뽑아냈다.

-1은 마지막 원소가 아니라

그냥 0보다 작은 출발점일 뿐이다.

 

이렇게 해서 만약 파란색 파티션이

A의 가장 끝에 도달하고 끝난다면

더이상 increase를 계산할 이유가 없지만

마지막에 더 increase를 계산해야하는 경우

계산해주고 리턴하면 된다.