JavaScript push와 unshift

Intro

프로그래머스 문제를 풀던 중, 시간초과에 봉착했다.

로직은 충분히 간결하다고 생각했기 때문에, '혹시 여기인가?' 라고 생각했던 곳이 문제였었고, 당연하다고 생각했던 부분에 대한 착각이었다.

1. 처음의 코드

문제는 다음과 같다.

집합의 원소의 개수 n과 모든 원소들의 합 s가 매개변수로 주어질 때
각 원소의 곱이 최대가 되는 집합을 return 하는 solution 함수를 완성

몫과 나머지를 구해서, n제곱에 가깝게 배열을 구성하면 된다는 논리를 바탕으로 코드를 짰는데, 자꾸만 시간초과가 발생했다.

function solution(n, s) {
  if (s < n) return [-1];

  const q = Math.floor(s / n);
  const r = s % n;

  const answer = [];

  for (let i = 0; i < r; i++) {
    answer.push(q + 1);
  }

  for (let i = 0; i < n - r; i++) {
    answer.unshift(q);
  }

  return answer;
}

2. 수정한 코드

JavaScript의 Array는 push와 unshift 모두 사용가능하기 때문에 Java의 Priority Queue와 비슷하다고 착각하고 있던 것이 문제였다.

시간 초과의 원인은 unshift()의 시간복잡도에 있었다.

unshift()는 배열의 앞쪽의 원소를 추가할 때마다 원소들을 한 칸씩 밀어야 하기 때문에 O(n)의 시간이 걸리는 반면, push()는 배열의 마지막 인덱스에 원소를 추가하기 때문에 O(1)의 시간 복잡도를 가진다.

이 차이를 이해하고 문제를 해결했다.

function solution(n, s) {
  if (s < n) return [-1];
  if (s === n) return new Array(n).fill(1);

  const q = Math.floor(s / n);
  const r = s % n;

  const answer = [];

  for (let i = 0; i < n - r; i++) {
    answer.push(q);
  }

  for (let i = 0; i < r; i++) {
    answer.push(q + 1);
  }

  return answer;
}

Intro

1. 처음의 코드

2. 수정한 코드

Reference