Codility Lesson4 - MaxCounters

Codility Lesson4 - MaxCounters

https://app.codility.com/demo/results/training7F6A9P-Z4M/

Test results - Codility

 

문제

You are given N counters, initially set to 0, and you have two possible operations on them:

• increase(X) − counter X is increased by 1,
• max counter − all counters are set to the maximum value of any counter.

A non-empty array A of M integers is given. This array represents consecutive operations:

• if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
• if A[K] = N + 1 then operation K is max counter.

For example, given integer N = 5 and array A such that:

A[0] = 3 A[1] = 4 A[2] = 4 A[3] = 6 A[4] = 1 A[5] = 4 A[6] = 4

the values of the counters after each consecutive operation will be:

(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)

The goal is to calculate the value of every counter after all operations.

Write a function:

def solution(N, A)

that, given an integer N and a non-empty array A consisting of M integers, returns a sequence of integers representing the values of the counters.

Result array should be returned as an array of integers.

For example, given:

A[0] = 3 A[1] = 4 A[2] = 4 A[3] = 6 A[4] = 1 A[5] = 4 A[6] = 4

the function should return [3, 2, 2, 4, 2], as explained above.

Write an efficient algorithm for the following assumptions:

• N and M are integers within the range [1..100,000];
• each element of array A is an integer within the range [1..N + 1].

 

정답

def solution(N,A):
    arr= [0]*N
    for i in (A):
        if i == N+1:
            arr = [max(arr)] * len(arr)
        else:
            arr[i-1]+=1
    return arr

 

결과

 

-> 런타임이 너무 오래 걸림. 다른 블로그 보고 참고

---

정답-Retry

def solution(N,A):
    savemaximum = 0

    maximum = 0
    counter = [0]*N
    for i in range(len(A)):
        if A[i]<=N:
            if counter[A[i]-1]<savemaximum:
                counter[A[i]-1]=savemaximum
            '''위의 과정을 거치는 이유. savemaximum 값이 바귀는 경우는 A[i]<=N일 때만 갱신
            그 전까지는 계속 0을 유지하고 있어서 savemaximum보다 값이 작아질 경우는 없음.
            A[i]<=N 한 번 작용하면 savemaximum 값은 갱신되고 해당 값을 우선반영하지 않고
            진행하면 결과에 틀린 영얗을 미칠 수 있음/ 따라서 savemaximum보다 작은 값을 지녀서 
            A[i]<=N일 때 갱신이 되고, 이후에 counter[A[i]-1]+=1 이 적용되는 숫자에 한해서만
            먼저 최대값에 따른 값 갱신이 진행됨.'''
            counter[A[i]-1]+=1
            maximum = max(counter[A[i]-1],maximum)
        else:# N보다 큰 수가 들어오면 maximum으로 동기화
            savemaximum = maximum
    for i in range(N):
        if counter[i]<savemaximum:
            counter[i]=savemaximum
    return counter

가장 이해가 안되었던 부분 - 이 부분을 가장 오래 붙들고있었으며, 가장 이해가 안되었음

if counter[A[i]-1]<savemaximum:
    counter[A[i]-1]=savemaximum

해당 식이 어떻게 A[i]==N+1 을 충족한 다음 counter[A[i]-1]+=1 항목에만 적용되는지 이해하는 것이 어려웠음. 다만 다시 생각해보면 A[i]==N+1바로 다음 counter[A[i]-1]+=1 항목에만 적용되는 것이 아니라, A[i]==N+1이 당시에 최대값보다 작은 수를 가지고 있고 그 이후에 counter[A[i]-1]+=1을 해야하는 모든 항목에 적용됨. 조금 더 자세한 내용은 위 코드의 주석에 존재

 

결과-Retry