Codility - Max Counters
All Posts

Codility - Max Counters

Max Counters

문제

숫자 N이 주어진다. 이 숫자 N은 모든 요소가 0인 길이 N인 배열을 의미한다. 그리고 배열 A가 존재한다.

숫자 N이 5로 주어지고, 배열 A는 [3, 4, 4, 6, 1, 4, 4] 라고 가정하자.

초기 값 [0, 0, 0, 0 0]
A[0] = 3, 3번째 (3-1번째) 요소의 크기를 1 늘린다.
- [0, 0, 1, 0, 0]
A[0] = 4, 4번째 (4-1번째) 요소의 크기를 1 늘린다.
- [0, 0, 1, 1, 0]
A[0] = 4, 4번째 (4-1번째) 요소의 크기를 1 늘린다.
- [0, 0, 1, 2, 0]
A[0] = 6, 모든 숫자의 크기를 현재 가장 큰 값으로 맞춘다.
- [2, 2, 2, 2, 2]
....

최종 결과는 
- [3, 2, 2, 4, 2]

풀이

function solution(N, A) {
    // 0으로 초기화된 길이 N의 배열을 만든다.
    const array = Array(N).fill(0)
    // 배열 내 최대 값
    let max = 0
    // 마지막 max counter의 기준이 되었던 수
    let maxCounter = 0
    for (let i=0; i<A.length; i++) {
        // 모든 숫자를 올려야 하는 경우
        if (A[i] > N) {
            // maxCounter에 다같이 올라가는 최대 숫자를 저장해 둔다.
            maxCounter = max

        // 하나씩만 올리면 되는 경우        
        } else {
            
            // 현재 숫자가 maxCounter보다 작을 경우 maxCounter로 초기화 한다.
            if (array[A[i] - 1] < maxCounter) {
                array[A[i] - 1] = maxCounter
            }
            
            // 그리고 +1을 한다
            array[A[i] - 1] += 1   
            
            
            // 이렇게 새롭게 세팅된 숫자가 배열의 최대값인지 확인한다.
            if (max < array[A[i] - 1]) {
                max = array[A[i] - 1]
            }
            
        }
    }

    // 배열의 값이 maxCounter보다 작다면 그 값으로 리턴한다.   
    return array.map((i) => i < maxCounter ? maxCounter : i)
}

해설

처음에는 저 maxCounter액션을 array를 map을 돌면서 +1 을 해줬더니 timeout 에러가 났다. 그도 그럴 것이 안그래도 배열을 n회 순환하는데, +1 을하면서 또 순환하면 복잡도가 O(N^2)이 될 것이기 때문이다. 그래서 최대한 배열을 한번에 순환하는 방식으로 해결하고자 노력했다.

https://app.codility.com/demo/results/training7YGA6S-4D7/