[LeetCode 238] Product of Array Except Self - 나누기 없이 배열 곱셈 구하기

[LeetCode] Product of Array Except Self - 나누기 없이 배열 곱셈 구하기

📌 문제 설명

LeetCode의 "Product of Array Except Self" 문제는 각 요소를 제외한 나머지 요소들의 곱을 구하는 문제입니다.

• 단, 나누기 연산(/)은 사용할 수 없음
• 시간 복잡도는 O(N) 이어야 함
• 추가 공간 O(1)만 사용 가능 (answer[] 외의 추가 배열은 금지)

---

📌 문제 해결 과정

✅ 잘못된 접근 (나누기 활용 방법)

처음에는 전체 곱을 구한 후, 각 요소를 나누는 방식이 떠오를 수 있습니다.

const totalProduct = nums.reduce((acc, val) => acc * val, 1);
return nums.map(num => totalProduct / num); // ❌ 나누기 연산 금지

하지만 문제에서 나누기 연산을 사용할 수 없으므로 적용 불가합니다.

---

📌 올바른 해결 방법 (Prefix & Suffix 곱 활용)

🚀 핵심 아이디어

1. 왼쪽 곱(prefix product) 저장 → answer[i]에 nums[i] 왼쪽 요소들의 곱을 저장
2. 오른쪽 곱(suffix product) 계산 & 최종 결과 반영 → answer[i]에 nums[i] 오른쪽 요소들의 곱을 곱함

이렇게 하면 O(N) 시간 복잡도로 나누기 없이 문제를 해결할 수 있습니다.

---

📌 최적화된 코드 (O(N) 시간, O(1) 공간)

export function productExceptSelf(nums: number[]): number[] {
  const n = nums.length;
  const answer = new Array(n).fill(1);

  // 1️⃣ 왼쪽 곱(prefix product) 저장
  let left = 1;
  for (let i = 0; i < n; i++) {
    answer[i] = left;
    left *= nums[i]; // 왼쪽 누적 곱 계산
  }

  // 2️⃣ 오른쪽 곱(suffix product) 계산 & 최종 결과 저장
  let right = 1;
  for (let i = n - 1; i >= 0; i--) {
    answer[i] *= right;
    right *= nums[i]; // 오른쪽 누적 곱 계산
  }

  // 3️⃣ -0 방지 처리
  return answer.map((val) => (Object.is(val, -0) ? 0 : val));
}

---

📌 예제 분석

입력: [1, 2, 3, 4]

1️⃣ 왼쪽 곱 계산

i nums[i] left answer[i] (왼쪽 곱)

0	1	1	1
1	2	1	1
2	3	2	2
3	4	6	6

✅ answer = [1, 1, 2, 6]

2️⃣ 오른쪽 곱 계산 & 최종 값 적용

i nums[i] right answer[i] (최종)

3	4	1	6 × 1 = 6
2	3	4	2 × 4 = 8
1	2	12	1 × 12 = 12
0	1	24	1 × 24 = 24

✅ 최종 answer = [24, 12, 8, 6]

---

📌 Jest 테스트 코드

describe("Medium 238: Product of Array Except Self", () => {
  it("calculates the product of array except self for positive numbers", () => {
    expect(productExceptSelf([1, 2, 3, 4])).toEqual([24, 12, 8, 6]);
  });

  it("handles arrays containing zero", () => {
    expect(productExceptSelf([-1, 1, 0, -3, 3])).toEqual([0, 0, 9, 0, 0]);
  });

  it("handles multiple zeros in the array", () => {
    expect(productExceptSelf([0, 0, 2, 3])).toEqual([0, 0, 0, 0]);
  });

  it("handles arrays with a single zero", () => {
    expect(productExceptSelf([4, 0, 5])).toEqual([0, 20, 0]);
  });

  it("handles all elements being zero", () => {
    expect(productExceptSelf([0, 0, 0])).toEqual([0, 0, 0]);
  });

  it("handles negative numbers correctly", () => {
    expect(productExceptSelf([-1, -2, -3, -4])).toEqual([-24, -12, -8, -6]);
  });

  it("handles a single element (edge case)", () => {
    expect(productExceptSelf([42])).toEqual([1]);
  });

  it("handles two elements", () => {
    expect(productExceptSelf([3, 5])).toEqual([5, 3]);
  });

  it("handles negative numbers with zero", () => {
    expect(productExceptSelf([-1, 0, -2, -3])).toEqual([0, -6, 0, 0]);
  });
});

✅ 다양한 입력 케이스 검증하여 정확성 확보
✅ 테스트 케이스 추가 (0 포함, 음수 포함, 작은 배열 예외 처리)

---

📌 시간 & 공간 복잡도

연산 복잡도 설명

시간 복잡도	O(N)	배열을 2번 순회 (왼쪽 곱, 오른쪽 곱)
공간 복잡도	O(1)	answer[] 외의 추가 공간 사용 없음

✅ 추가 공간 O(1)을 유지하면서 나누기 없이 해결 가능! 🚀

---

📌 최종 정리

• 나누기 없이 해결해야 함 → 왼쪽 곱(prefix), 오른쪽 곱(suffix) 활용
• 배열을 2번 순회(O(N))하여 각각 왼쪽/오른쪽 곱을 계산
• 추가 공간 O(1) 유지 (출력 배열 제외하고 추가 배열을 사용하지 않음)

💡 이제 비슷한 문제를 만나면 "Prefix & Suffix 곱"을 우선 고려해 보세요! 🚀