Codility - MaxCounters [Python]

😅 문제 

 

- A라는 리스트를 받아 하나씩 순회하며 그 요소 값이 N보다 작으면 N번째 개수를 하나 증가시키고, N+1이면 지금까지중 가장 큰 값으로 모든 수를 조정해준다.

 

 

🤔 문제 상황 

 

- A라는 리스트를 받아 하나씩 순회하며 그 요소 값이 N보다 작으면 N번째 개수를 하나 증가시키고, N+1이면 지금까지중 가장 큰 값으로 모든 수를 조정해준다.

 

 

🧐 해결 전략 

 

- 첫번째 :

  cache를 만들어 문제 상황을 그대로 구현

 

- 두번째:

  변수를 두개 만들어 최대값을 매번 갱신해줄 최대값, N+1이 진행되었을 때 최대값을 저장할 최대값으로 정한다.

  가장 중요한 것은 마지막에 O(N)으로 전체 탐색을 하며 저장된 최대값보다 작은 값을 저장된 최대값으로 갱신하는 것이다.

  이를 위해 부분 갱신을 해주기 위해 N+1 이후 갱신은 +=1 이 아니라 = mx+1로 해준다.

 

 

🎰 코드 

- 첫번째 코드 (타임아웃 발생 66%) O(N*M)

def solution(N, A):
    ck = [0 for _ in range(N)]
    mx = 0
    for i in range(len(A)):
        if A[i] == N+1:
            ck = [mx for _ in range(N)]
            continue
        ck[A[i]-1] += 1
        if ck[A[i]-1] > mx:
            mx = ck[A[i]-1]
    return ck

 

- 두번째 코드 (100%) O(N+M)

def solution(N, A):
    counters = [0 for _ in range(N+1)]
    # 임시 최대값
    temp_mx = 0
    # 저장될 최대값
    mx = 0
    
    for x in A:
        # N+1 일 땐 저장될 최대값을 갱신해준다.
        if x == N+1 :
            mx = temp_mx
        # N+1보다 작을 경우 
        else :
            # x 이전의 경우에 N+1이 나왓다면 mx가 갱신되었을 것이고 아니면 0이므로 1만 증가시켜준다.
            if counters[x] < mx :
                counters[x] = mx + 1
            # counters[x]가 mx보다 크다면 1만큼만 올려야한다. 이미 최대값인데 mx+1 만큼 증가될 수 있다. 
            else:
                counters[x] += 1
            # counters[x] 가 부분 최대값보다 크다면 갱신해준다.
            if counters[x] > temp_mx :
                temp_mx = counters[x]
            
    # 만약 N+1 이 나온 이후에 증가된 부분이 있다면 위에 if문에서 이미 mx + 1 로 처리가 되었다. 
    # 즉 mx보다 작은 모든 값은 N+1이 나온 이후에 갱신된 적이 없다는 뜻이므로 전체를 += mx가 아니라 = mx로 갱신하면 된다.
    for i in range(1, len(counters)):
        if counters[i] < mx :
            counters[i] = mx
    return counters[1:]

 

 

🧙‍♂️ 해설

max, list comprehension 등이 O(N)이라는 생각을 못했다. 갱신을 위해 변수를 활용할 필요가 있다.

 

📈 새로 학습한 것 & 실수 

- 첫번째 코드의 경우 for문 안에 ck를 재설정 하는데서 속도 이슈가 생긴 것 같다.

 

- 대략적으로 빅오와 범위로 시간 측정을 하는 습관을 기를 필요가 있다.

 

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