자바스크립트 정수 배열에서 두 수의 최대 곱 구하기

정수 배열을 첫 번째이자 유일한 인수로 받는 자바스크립트 함수를 작성해야 합니다. 이 함수는 배열 내 두 요소를 곱했을 때 얻을 수 있는 최대 곱(maximum product)을 반환해야 하며, 반드시 선형 시간 O(n)과 상수 공간 O(1)이라는 조건을 만족해야 합니다.

접근 방법

단순히 생각하면 배열에서 가장 큰 두 수를 곱하면 될 것 같지만, 음수가 포함된 경우에는 주의해야 합니다. 음수끼리 곱하면 양수가 되기 때문에, 절댓값이 큰 음수 두 개의 곱이 양수 두 개의 곱보다 더 커질 수 있습니다.

따라서 배열을 한 번만 순회하면서 다음 네 개의 값을 동시에 추적하는 것이 핵심입니다.

a, b : 배열에서 가장 큰 값과 두 번째로 큰 값
c, d : 배열에서 가장 작은 값과 두 번째로 작은 값

순회가 끝난 뒤 Math.max(a * b, c * d)를 반환하면 양수와 음수가 섞여 있는 경우에도 항상 올바른 최대 곱을 구할 수 있습니다.

예시

입력 배열이 다음과 같다면,

const arr = [3, 9, 2, 1, 0];

출력은 다음과 같아야 합니다.

3 × 9 = 27이 만들 수 있는 곱 중 가장 크기 때문입니다.

구현 코드

const arr = [3, 9, 2, 1, 0];

const maxPairProduct = (arr = []) => {
  // 가장 큰 두 수를 저장할 변수
  let a = -Infinity, b = -Infinity;
  // 가장 작은 두 수를 저장할 변수
  let c = Infinity, d = Infinity;

  for (const n of arr) {
    // 최댓값 두 개 갱신
    if (n >= a) {
      b = a;
      a = n;
    } else if (n >= b) {
      b = n;
    }
    // 최솟값 두 개 갱신
    if (n <= d) {
      c = d;
      d = n;
    } else if (n <= c) {
      c = n;
    }
  }

  return Math.max(a * b, c * d);
};

console.log(maxPairProduct(arr)); // 27

코드 설명

변수 a와 b는 지금까지 확인한 값 중 가장 큰 값과 두 번째로 큰 값을, 변수 c와 d는 가장 작은 값과 두 번째로 작은 값을 저장합니다. 각각 -Infinity와 Infinity로 초기화하여 어떤 값과도 비교할 수 있도록 합니다.

배열의 각 요소 n에 대해 다음을 수행합니다.

n이 현재 최댓값 a보다 크거나 같으면, 기존 a를 b로 밀어내고 n을 새 최댓값으로 저장합니다.
n이 b보다 크거나 같으면 b만 갱신합니다.
같은 방식으로 n이 최솟값 d보다 작거나 같으면 기존 d를 c로 밀어내고, 그렇지 않고 c보다 작으면 c를 갱신합니다.

이렇게 하면 단 한 번의 순회로 필요한 네 개의 극값을 모두 얻을 수 있으며, 마지막에 두 최댓값의 곱과 두 최솟값의 곱 중 더 큰 값을 반환하면 됩니다.

복잡도 분석

시간 복잡도 : O(n) — 배열을 딱 한 번만 순회합니다.
공간 복잡도 : O(1) — 추가로 사용하는 변수는 네 개뿐입니다.

출력

콘솔 출력 결과는 다음과 같습니다.