[Codility] MaxCount (python3)

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

주어진 배열 A의 원소의 값에 따라 주어진 N개의 counter를 만들어 리턴해주는 문제.

A의 원소 X 가
1<=X<=N 인 경우에는 K번째 counter를 +1
X == N+1 인 경우에는 모든 counter를 현재 max카운터로 변경

간단하게 생각하면 이중 for문으로 풀 수 있겠지만, 원소의 최대 개수가 10만개이기 때문에 이중포문으로 풀면 효율성에서 실패할 것이다. 그러니 최대한 반복문 내부에 반복문은 피하고, 한 번의 반복문과 반복문 밖에서의 로직으로 문제를 해결해야 한다.

나의 첫 번째 풀이

매 반복문마다 counter리스트의 최대값을 구하여 temp변수에 저장한다.
그리고 이중포문을 피하려면 포문을 돌아야 하는 X=N+1일 때 최소값을 기억해 주었다가 반복문이 다 끝나면 해당 값을 더해주는 방식으로 하였다.

def solution(N, A):
    # write your code in Python 3.6

    counter_list = [0] * N
    temp_max = 0
    min_in_list = 0
    for i in range(len(A)):
        if A[i] <= N:
            if counter_list[A[i]-1]  > min_in_list:
                counter_list[A[i]-1] += 1 # 그냥 +1
            else:
                counter_list[A[i]-1] = min_in_list + 1 # 최소값 +1

            temp_max = max(counter_list)    
        elif A[i] == N+1:
            min_in_list = temp_max

    for j in range(N):
        if counter_list[j] < min_in_list:
            counter_list[j] = min_in_list
     
    return counter_list
    pass

정답률은 66%. 시간을 더 줄여야 했다. python의 max() 함수의 시간 복잡도는 O(N)이다. N개의 counter 리스트를 M번을 반복하는 for문 내부에서 사용되니 시간복잡도가 O(M*N)이 나온다.
이 함수를 최소한으로 사용하거나 사용하지 않는 방법을 찾아야 할 것 같다.

나의 두 번째 풀이

최대값을 매 반복문마다 구하지 않고 X=N+1인 경우에만 구해서 min 값에 대입해준다.

def solution(N, A):
     # write your code in Python 3.6
    
    counter_list = [0] * N
    temp_max = 0
    min_in_list = 0
    for i in range(len(A)):
        if A[i] <= N:
            if counter_list[A[i]-1]  > min_in_list:
                counter_list[A[i]-1] += 1
            else:
                counter_list[A[i]-1] = temp_max + 1
        elif A[i] == N+1:
            temp_max = max(counter_list)
            min_in_list = temp_max

    for j in range(N):
        if counter_list[j] < min_in_list:
            counter_list[j] = min_in_list
       
    return counter_list

    pass

역시 정답률 66프로. max()를 사용하지 않고 최대값을 찾아야 한다.

나의 세 번째 풀이

첫 번째 방법과 동일하게 매 반복문마다 최대값을 찾는다. 하지만 max() 메소드를 사용하는 것이 아니라 temp값과 비교하는 방법으로 최대값을 구한다.

def solution(N, A):
    # write your code in Python 3.6

    counter_list = [0] * N
    temp_max = 0
    min_in_list = 0

    for i in range(len(A)):
        if A[i] <= N:
            if counter_list[A[i]-1]  > min_in_list:
                counter_list[A[i]-1] += 1
            else:
                counter_list[A[i]-1] = min_in_list + 1
        
            if counter_list[A[i]-1] > temp_max:
                temp_max = counter_list[A[i]-1]    
        elif A[i] == N+1:
            min_in_list = temp_max

    for j in range(N):
        if counter_list[j] < min_in_list:
            counter_list[j] = min_in_list
    
    return counter_list

    pass

결과는 O(N+M)으로 정답.

효율성 때문에 생각보다 까다로운 문제였다. 다음부터 이런 문제를 마주한다면 위에 캡쳐한 것처럼 차근차근 그리면서 풀면 도움이 될 것 같다.