[Codility - Counting Elements] MaxCounters

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

MaxCounters coding task - Learn to Code - Codility

- 백준 기준 실버4 정도 되는 문제가 아닐까 생각한다.

 

- N size의 배열을 counter라 하고, A의 각 element들이 가리키는 k번째의 counter 갯수를 1 올려주면 된다. 이때, k가 N+1인 경우 모든 counter의 값을 최대값으로 update 해 주어야 한다.

 

- N과 A의 size가 최대 100,000이므로, 문제에서 하라는대로 정직하게 구현하면 시간초과가 난다. (A의 모든 k가 N+1이라고 가정해보자. 그러면 매 번 모든 counter들을 update해 주어야 하므로 총 N^2의 시간이 걸리기 때문이다.

function solution(N, A) {
    let arr = new Array(N).fill(0)
    let maxCount = 0
    let tempMaxCount = 0
    for(let i = 0; i < A.length; i++){
        if(A[i] === N+1){
            maxCount = tempMaxCount
        } else {
            arr[A[i]-1] = Math.max(arr[A[i]-1]+1, maxCount+1)
            tempMaxCount = Math.max(tempMaxCount, arr[A[i]-1])
        }
    }
    for(let i = 0; i < arr.length; i++){
        arr[i] = Math.max(arr[i], maxCount)
    }
    return arr
}

 

- N+1을 만났을 때, counter를 모두 update하지 않는다. 대신 maxCount를 두고 이 maxCount를 지속적으로 update를 해 준다.

 

- N+1을 만나지 않았을 때는, 마지막 maxCount로부터 +1을 한 값이나, 현재 counter의 값 +1 중 큰 수를 update 해준다. 전자의 경우는 N+1을 만난 이후 한 번도 update 되지 않았을 때 시행되는 로직이며, 후자는 그 외의 경우이다.

 

- 모든 연산을 마치면, 이제 가장 최근의 maxCount과 각 counter들의 현재 값을 비교해서 더 큰 값을 대입 해 준다.