[코딩테스트] Codility 3-1 TapeEquilibrium (Javascript)

문제 링크 : https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/

 

솔루션1

점수 : 53%
시간복잡도 : O(N*N)

 

코드 작성

i의 값을 1부터 N-1 까지 for문 돌리기

i 기준으로 slice를 해서 전달인자를 두 개의 배열로 나누기

두 배열의 차이를 선언된 arr 배열에 담고, 최소값을 리턴하기

 

function solution(A) {

  let arr = [];
  let Length = A.length
   
  function sumArr (A) {
    let result = A.reduce((acc,cur)=>{return acc+cur})
    return result;
  }

  for (let i=1; i<Length; i++) {
    let first = A.slice(0,i)
    let second = A.slice(i,Length)
    let difference = Math.abs(sumArr(first) - (sumArr(second)))
      arr.push(difference);
    }
    return Math.min(...arr)
  }

 

리뷰

Correctness tests에서는 모든 정답을 맞추었다.

그러나 Performance tests에서는 시간복잡도 문제로 Error가 발생했다.

 

반복문의 시간복잡도는 O(N)이며, slice 메소드의 시간복잡도 또한 O(N)이다.

반복문 내에서 slice 메소드를 사용하면 총 시간복잡도는 O(N^2)가 되어 높은 점수를 받지 못한다.

시간복잡도를 낮출 수 있도록 코드를 수정해보았다.

 

 

솔루션2

점수 : 100%
시간복잡도 : O(N)

 

코드 작성

P=1 기준으로 첫번째 배열의 합(first)과 두번째 배열의 합(second)을 초기값으로 선언 후 할당

두 배열의 합의 차이(minDiffer) 또한 초기값으로 선언 후 할당

반복문을 순회하며 first와 second의 값을 변경하고, 그 차이(differ)를 구하기

differ가 minDiffer보다 작으면, differ 값을 minDiffer에 할당하기

minDiffer 값을 리턴

 

function solution(A) {

  let total = A.reduce((acc, cur) => acc + cur)
  let first = A[0]
  let second = total - first
  let minDiffer = Math.abs(first - second);

  for (let i=1; i<A.length-1; i++) {
    first += A[i];
    second -= A[i]
    let differ = Math.abs(first - second);
    if (differ<minDiffer) minDiffer = differ
  }
  return minDiffer;
}

 

리뷰

시간복잡도가 O(N)이 되어 Performance tests를 모두 통과

slice 메소드 또한 시간복잡도에 영향을 주기 때문에, 경우에 따라 반복문 내에서는 사용 지양하기