[코딩테스트] Codility 4-3 MaxCounters (JavaScript)

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

 

Solution 1

정답률 : 100%

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

 

코드작성

우선 결과를 담을 길이가 N인 arr 엘리먼트를 선언해야 한다.

arr 엘리먼트의 최대값인 max 변수와 max counter의 기준이 될 변수 maxCounter도 따로 선언했다.

 

시간복잡도는 O(N^2)보다 효율적인 코드를 작성해야 한다.

따라서 for 문 내에서는 조건문을 통해 값을 할당하는 코드만 작성했고,

시간복잡도가 O(N)이 되는 Math.max, fill 등의 메소드는 사용하지 않았다.

 

function solution(N, A) {

  let arr = Array(N).fill(0);  // 결과를 담을 arr 배열 선언
  let max = 0;                 // 배열 내 최대값 max 선언
  let maxCounter = 0;          // max counter의 기준이 될 변수 maxCounter 선언

  // 반복문으로 A의 엘리먼트 순회하기
  for (let ele of A) {
  
    if (ele>N) {  // A의 엘리먼트가 N보다 큰 경우
     
      // max counter을 하기 위해 maxCounter변수에 max 선언
      maxCounter = max;  
      
    } else {
    
      const idx = ele-1
      
      // arr의 엘리먼트가 maxCounter보다 작으면, maxCounter를 할당
      if (arr[idx] < maxCounter) arr[idx] = maxCounter;
      
      // 문제 조건에 따라 엘리먼트 +1
      arr[idx] += 1;
      
      // 해당 엘리먼트가 max보다 크면, max에 엘리먼트를 할당
      if (arr[idx] > max) max=arr[idx] 
    }
  }

  // 반복문에서 조회되지 못해서 max counter를 적용시키지 못한 엘리먼트가 있을 수 있음
  // 따라서 maxCounter보다 작은 엘리먼트가 있다면 maxCounter를 할당하기
  let result = arr.map((el)=> el<maxCounter ? maxCounter : el)
  
  return result;
}

 

 

Solution 2

정답률 : 77%

 

코드 작성 & 리뷰

Correctness tests : 모든 정답을 맞춤

Performance tests : 2개의 케이스에서 timeout 발생

 

max count를 진행할 경우, 반복문 내에서 fill 메소드 사용

fill 메소드의 시간복잡도는 O(N)이므로 시간복잡도가 증가함

 

max count를 진행할 경우에만 fill 메소드를 사용하기 때문에 문제가 없을 것이라고 생각했으나,

결과적으로는 성능 저하의 원인이 됨

 

function solution(N, A) {

  let arr = Array(N).fill(0);
  let Max = 0;
  
  for (let ele of A) {
    
    // A의 엘리먼트가 N보다 커서 max count를 실행할 경우, fill 메소드 사용
    if (ele>N) {
      arr.fill(Max)
    } else {
      const idx = ele - 1
      arr[idx] +=1
      if (arr[idx] > Max) Max=arr[idx]
    }
  }
  return arr;
}