[Javascript] Codility Lesson 4 - MaxCounters

 

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

 

문제 요약:

• N개의 0으로 채워진 a배열과, 임의의 수로 채워진 b배열이 있다고 가정
• b배열을 순회하며 요소의 값에 따라 a배열의 요소 + 1 (increase)
• b요소의 값이 N + 1이면 a배열의 모든 요소를 max 값으로 변경 (maxCounter)

function solution(N, A) {
    let nCounter = new Array(N).fill(0);

    const increase = (arr, x) => {
        arr[x - 1] += 1;
        return arr;
    }
    const maxCounter = (arr) => {
        let max = Math.max(...arr);
        return new Array(N).fill(max);
    }

    for (let i = 0; i < A.length; i++) {
        if (A[i] <= N) {
            nCounter = increase(nCounter, A[i]);
        } else {
            nCounter = maxCounter(nCounter);
        }
    };

    return nCounter;
}

https://app.codility.com/

처음 풀었을 때 제출한 답에서 시간 복잡도가 O(N*M)이 나왔다. 순환문 안에서 또 순환문을 돌렸기 때문에 효율성이 떨어졌을 것으로 판단.

 

 

개선 시도 1. 배열을 객체 타입으로 변환하여 key-value로 탐색할 수 있게 하기

결과: 시간 복잡도는 똑같이 O(N*M). 벤치마크 프로그램을 통해 실행해보면 위에 코드보다 속도가 더 느리게 나옴. 

function solution(N, A) {
    let nCounter = new Array(N).fill(0);
    let dictionary = A.reduce((prev, curr, i) => {
      prev[i] = curr;
      return prev;
    }, {});

    const increase = (arr, x) => {
        arr[x - 1] += 1;
        return arr;
    }
    const maxCounter = (arr) => {
        let max = Math.max(...arr);
        return new Array(N).fill(max);
    }

    for (let i = 0; i < A.length; i++) {
        if (A[i] <= N) {
            nCounter = increase(nCounter, dictionary[i]);
        } else {
            nCounter = maxCounter(nCounter);
        }
    };

    return nCounter;
}

 

 

개선 시도 2. max값 저장하기

결과: 속도 개선(40% -> 60%) 됐으나 배열 요소가 10000개 이상인 경우 여전히 Timeout 발생

function solution(N, A) {
    let nCounter = new Array(N).fill(0);
    let max = 0;

    const increase = (arr, x) => {
        arr[x - 1] += 1;
        max = arr[x - 1] > max ? arr[x - 1] : max;
        return arr;
    }
    const maxCounter = () => {
        return new Array(N).fill(max);
    }

    for (let i = 0; i < A.length; i++) {
        if (A[i] <= N) {
            nCounter = increase(nCounter, A[i]);
        } else {
            nCounter = maxCounter();
        }
    };

    return nCounter;
}

https://app.codility.com/

 

 

개선 시도 3. maxCounter를 한 번만 실행시키기. 다른 분들의 풀이를 보니 maxCounter를 1번만 실행시키는 게 속도를 줄이는데 키포인트였다. maxCounter라는 함수는 결국 배열의 처음부터 끝까지를 순환하며 max값으로 치환하는 일을 하기 때문에, 여러 번 실행할 경우 배열의 길이가 길어질수록 그에 비례하여 처리 속도는 느려질 것이다. 

결과: 시간복잡도 O(N + M). 

function solution(N, A) {
    let nCounter = new Array(N).fill(0);
    let tempMax = 0;
    let max = 0;

    const increase = (arr, x) => {
        arr[x - 1] = arr[x - 1] > max ? arr[x - 1] + 1 : max + 1;
        tempMax = arr[x - 1] > tempMax ? arr[x - 1] : tempMax;
        return arr;
    };

    for (let i = 0; i < A.length; i++) {
        if (A[i] <= N) {
            nCounter = increase(nCounter, A[i]);
        } else {
            max = tempMax;
        }
    };

    for(let i = 0; i < nCounter.length; i++) {
        nCounter[i] = nCounter[i] < max ? max : nCounter[i]
    }

    return nCounter;
}

https://app.codility.com/