(코딜리티) Lesson 4 : MaxCounters - Python

이번에 코딜리티 문제 풀면서, 못 풀었네요... 아직 너무 부족합니다ㅠ

 

문제 : app.codility.com/programmers/lessons/4-counting_elements/

4. Counting Elements lesson - Learn to Code - Codility

문제 해설

N인 정수와 M개의 배열인 A로 파라미터 2개가 주어질 것이며,

예를 들어, N = 5, 배열 A가 [3, 4, 4, 6, 1, 4, 4] 인 경우, 배열안의 숫자를 카운터 합니다.

(0, 0, 1, 0, 0)

(0, 0, 1, 1, 0)

(0, 0, 1, 2, 0)

(2, 2, 2, 2, 2)

(3, 2, 2, 2, 2)

(3, 2, 2, 3, 2)

(3, 2, 2, 4, 2)

 

이런 식으로 카운터 합니다.

 

여기서 4번째인 (2, 2, 2, 2, 2)는 주어진 N =5 보다 큰 6이므로 그 전에 카운터된 값중 제일 큰값으로 전체를 채웁니다.

그리고 마지막엔 (3, 2, 2, 4, 2)를 return 합니다.

제한 사항

N과 M은 1~100,000사이의 값을 가집니다.

A의 각 요소는 1~N+1의 값을 가집니다.

코드

def solution(N, A):
    r = N*[0] 	#counter를 담을 리스트
    m1 = 0 	#다음 최댓값이 나오기 전의 최댓값
    m2 = 0 	#for문마다 최댓값
    for i in A:
        if i <= N:
            r[i-1] = max(r[i-1] +1, m1 +1) 	#현재의 최댓값과 counter와 비교
            m2 = max(r[i-1], m2)  #counter와 최댓값과 비교
        else :
            m1 = m2 	#새로운 최댓값으로 업데이트
            
    return [m1 if f < m1 else f for f in r] 	#제일 처음 한번나오고 끝까지 안나온 값을 대비한 for문

해설

사실 for문안의 주석을 봐도 이해하기가 어려울 수 있습니다.

if문만 간단히 설명하자면, 

N=5인 경우에, 중간에 6의 값이 나온다면, m1 = m2의 값으로 변합니다. 

이유는 이전 루프에서 (1, 1, 5, 1, 1)이 나왔다면, m2 = 5가 될 것이고, m1도 5로 바꿔줘야 하며, 이후에 1이 나왔다면, 1+1 = 2가 아닌 최댓값 5 +1이 되어야 하기때문에, 새로 저장한 m1 +1과 기존의 r안에 있는 값과 비교해야합니다.

 

그리고, 여기서 끝이 아니라 이전 루프에서 (6, 5, 5, 10, 5)가 나오고, 6의값이 나왔다면, m1 = 10으로 바꿔야 합니다.

그리고 이후에 2가 나왔더라면, (6, 11, 5, 10, 5)식으로 진행되어야 합니다.

 

솔직히 처음에 시간문제로 계속 틀리다가, max(r)를 사용하는 것은 근본을 알게되면 max(r)또한 if문을 사용하여 최댓값을 구하는 것이니 시간이 오래걸릴 꺼라고 생각했습니다. 그리고, r[m]*N을 사용하는 방식도 결국 시간 문제에 영향을 끼칠 수 있기에 위와 같은 알고리즘으로 풀어야 합니다.

 

다른사람의 코드를 참고하면서 깨달은 것이 만약 N=5라고 할때 배열 A안에 6은 계속 나올 수 있다는 것이었습니다. ㅠㅠ 

이런 경우 A에 6은 1번만 나올거라는 고정관념에 박혀서 문제를 2시간 동안 못풀다가... 테스트 케이스를 찾아내고 이해를 할 수 있었습니다..