[Codility] MaxCounters (JavaScript)

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

MaxCounters coding task - Learn to Code - Codility

문제 요구사항:
N 길이인 배열에 조건에 따라 결과를 담아서 반환한다.
배열의 A[K]번째 위치에
조건 1. 주어진 A 배열의 A[K]가 N보다 작거나 같다면 결과 + 1을 하고,
N + 1과 같다면 모든 배열 원소를 그 배열 중 최대 값으로 변경한다.
내 풀이:

function increase(X) {
    return X + 1;
}
function maxCounter(N, arr) {
    const max = Math.max.apply(null, arr)
    return new Array(N).fill(max);
}
function solution(N, A) {
    let result = new Array(N).fill(0);
    for (let K = 0; K < A.length; K++) {
        if (A[K] <= N) {
            result[A[K] - 1] = increase(result[A[K] - 1]);
        }
        if (A[K] === N + 1) {
            result = maxCounter(N, result);
        }
    }
    return result;
}

- 채점 결과: 66%
 
분석: O(N*M)
Performance tests
- large_random1: large random test, 2120 max_counter operations
    TIMEOUT ERROR running time: 0.751 sec., time limit: 0.356 sec.
- large_random2: large random test, 10000 max_counter operations
    TIMEOUT ERROR running time: 3.208 sec., time limit: 0.404 sec. unning time: 0.751 sec.
- extreme_large: all max_counter operations
    TIMEOUT ERROR Killed. Hard limit reached: 6.000 sec.
원인:
- maxCounters 시에 매번 모든 배열의 원소를 업데이트하는 것보다는, 업데이트 해두어야 하는 값을 기억해두었다가 마지막에 한번 연산하도록 수정
 
수정한 풀이: 

function solution(N, A) {
    const arr = Array(N).fill(0);
    let max = 0, base = 0;

    for (const a of A) {
        if (a <= N) {
            const i = a - 1;
            arr[i] = Math.max(arr[i], base) + 1;
            max = Math.max(max, arr[i]);
        } else {
            base = max;
        }
    }
    return arr.map(v => Math.max(v, base));
}

- 채점 결과: 100%