Codility - Lesson 4 : MaxCounters

 

  문제에 나와있는대로 푼다면, A의 각 숫자를 순회하다가 N보다 큰 수를 만날 때 마다 여태까지 만났던 숫자들 중 가장 큰 숫자를 일괄적으로 채운 Array를 만들면서 진행하면 풀리기야 하겠지만, 직관적으로 이럴 경우 시간 복잡도에서 무조건 밀린다는 걸 알 수 있었다.

 

  그래서 다른 방법을 생각해야만 했다. 아래의 코드로 설명을 하자면 max는 여태까지 A를 순회하며 나왔던 숫자들 중 가장 큰 숫자고, maxCounter는 N보다 큰 수를 만났을 때 당시의 max 값이다. 위의 문제의 경우 A[2]까지 완료한 시점에서 max 값은 2이고, maxCounter는 0이었다가 A[3]을 완료하는 순간 max 값은 2, maxCounter 값도 2가 되게 된다.

 

  그리고 이걸 이용해서 첫 A.forEach를 아래 코드와 같이 수행한다. 하지만 미처 처리 되지 못한 케이스들이 있는데, 이걸 처리하기 위해 아래의 arr.forEach문을 수행한다.

 

 

function solution(N, A) {     let max = 0;     let maxCounter = 0;     const arr = new Array(N + 1).fill(0);     A.forEach(num => {         if (num <= N) {             if (arr[num] < maxCounter) {                 arr[num] = maxCounter + 1;             } else {                 arr[num] += 1;             }             if (max < arr[num]) {                 max = arr[num];             }         } else {             maxCounter = max;         }     });     arr.forEach((num, index) => {         if (num < maxCounter) {             arr[index] = maxCounter;         }     });     return arr.slice(1, arr.length); }

 

  결과