[LeetCode] 238. Product of Array Except Self

1ilsang
클라이밍 하실래염?
#algorithm#leetcode#medium#product
Published
problem

문제 링크

nums 배열 원소의 모두 곱한 값에서 해당 원소를 나눈 값을 출력하는 문제이다. 문제에서는 나눗셈하면 안 된다고 명시하고 있으므로 나눗셈하지 않고 풀어야 하는 게 포인트이다.

  1. 나눗셈을 하지 않아야 함.
  2. T=O(n), S=O(1)으로 풀어본다.

따라서 위의 두 가지를 목표로 이 문제를 해결해 보려고 한다.

Ideation

nums = [1, 2, 3, 4]의 경우를 살펴보자.

기대하는 정답은 [24, 12, 8, 6]이다. 해당 배열이 나오기 위해서는 전체 값의 곱(1*2*3*4 = 24)에 각자의 원소를 나누면 된다.

전체 곱에서 자신을 나누어 나오는 값은 자신을 제외한 모든 값의 곱과 동일하다.

e.g. 원소 3을 기준으로 한다면 1*2*3*4 / 3 === 1*2*4이다.

따라서 우리는 자신을 제외한 곱들의 왼쪽과 오른쪽을 곱해주면 정답이 된다는 것을 알 수 있다.

e.g. 원소 3을 기준으로 3의 좌/우의 곱은 1*2 * 4 = 8이다.

그러므로 왼쪽의 곱들과 오른쪽의 곱들을 기억해 두고 각 원소별 값을 출력해 주면 해결할 수 있다.

해당 원소까지의 왼쪽, 오른쪽 곱셈 값은 누적 배열을 활용하면 된다.

e.g. 원소 n 기준 왼쪽 [n-2, n-2 * n-1] * [n+1, n+1 * n+2] 오른쪽

const nums = [1, 2, 3, 4];
 
// @NOTE: 요소의 왼쪽까지의 곱을 기준으로 하기 때문에 첫 번째는 1으로하고 마지막 원소까지 곱할 필요는 없다.
const leftArr = [
  1,
  1 * nums[0],
  1 * nums[0] * nums[1],
  1 * nums[0] * nums[1] * nums[2],
]; // [1, 1, 2, 6];
 
// @NOTE: 요소의 오른쪽까지의 곱을 기준으로 하기 때문에 직관적으로 역순으로 한다.
const rightArr = [
  1 * nums[2] * nums[1] * nums[0],
  1 * nums[2] * nums[1],
  1 * nums[2],
  1,
]; // [24, 12, 4, 1];

Implementation(T=O(n), S=O(n))

위의 정리를 토대로 구현을 해보자.

  1. n 번째 원소의 왼쪽 곱의 값들을 저장한다.
  2. n 번째 원소의 오른쪽 곱의 값들을 저장한다.
  3. 전체 원소를 순회하며 n 번째 원소의 좌우 값의 곱을 저장한다.
  4. 리턴한다.
// Left Arr
const l = nums.reduce(
  (acc, cur) => {
    const last = acc[acc.length - 1]; // 누적값
    acc.push(cur * last); // 이전의 누적값 * 현재 원소를 통해 누적값을 채운다.
    return acc;
  },
  [1],
);
l.pop(); // 마지막 원소는 필요 없으므로 빼준다.
 
// Right Arr
const r = nums.reduce(
  (acc, _, index) => {
    const last = acc[0];
    const cur = nums[nums.length - index - 1];
    acc.unshift(cur * last);
    return acc;
  },
  [1],
);
r.shift();
 
// Left * Right Arr
const answers = nums.map((_, index) => l[index] * r[index]);
return answers;

위의 구현으로 문제를 해결할 수 있지만 공간 복잡도가 O(n)이기 때문에 더 최적화가 가능하다.

Implementation(T=O(n), S=O(1))

좌우 배열은 결국 마지막에 곱하기 위해서만 존재한다.

따라서 굳이 저장하지 않고 바로바로 곱해나가면 공간복잡도를 O(1)으로 줄일 수 있다.

const answers = [];
 
let last = 1;
// @NOTE: Step1. Answers 배열에 미리 왼쪽 곱 배열을 세팅
for (let i = 0; i < nums.length; i++) {
  const cur = nums[i];
  answers[i] = last;
  last *= cur; // 누적값 갱신
}
 
last = 1;
// @NOTE: Step2. Answers가 이미 좌측 곱 배열이므로 우측 값을 그대로 곱해주면 정답이 된다.
for (let i = nums.length - 1; i >= 0; i--) {
  const cur = nums[i];
  answers[i] *= last;
  last *= cur;
}
return answers;

NOTE: 어쨌든 answers 배열을 사용하므로 정확히는 O(n)이지만

LeetCode에서 return 배열(answers)이 아닌 추가 배열을 사용하지 않는다는 것으로 O(1)으로 취급하고 있다.

연속되는 곱셈의 합을 이용한 재밌는 문제였다.

그럼 이만~

📮 이 포스트에 관심 있으신가요? 이슈를 남겨주세요! 👍