[LeetCode][JAVA] 238. Product of Array Except Self

💡 문제

238. Product of Array Except Self (https://leetcode.com/problems/product-of-array-except-self/description/)

자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

 

📝 선행 개념

 

• Prefix/Suffix 누적곱: 각 인덱스 i에서의 답은 “왼쪽 모든 원소의 곱 × 오른쪽 모든 원소의 곱”.
• 공간 최적화 트릭: 출력 배열을 왼쪽 누적곱으로 먼저 채우고, 뒤에서 앞으로 오른쪽 누적곱을 곱해주면 보조 배열 없이 해결 가능.
• 나눗셈 금지: 문제 제약상 division 없이 O(n)에 처리.

 

---

🤓 문제 풀이

정수 배열 nums가 주어질 때, 각 위치 i에 대해 nums[i]를 제외한 나머지 모든 원소의 곱을 구한다.
ans[i] = (i 왼쪽 구간의 곱) × (i 오른쪽 구간의 곱)을 이용한다.

🔨 문제 설명

• 입력: 정수 배열 nums (2 <= nums.length <= 1e5, -30 <= nums[i] <= 30)
• 출력: 길이가 같은 정수 배열 ans, 단 ans[i] = ∏_{j≠i} nums[j]
• 제약: 나눗셈 사용 금지, 시간 O(n), 추가 공간 O(1)(출력 배열 제외)

예)

• nums = [1,2,3,4] → [24,12,8,6]
• nums = [-1,1,0,-3,3] → [0,0,9,0,0]

---

🔨 접근 방법

1. 왼→오(prefix):
   • prefix를 1로 시작, ans[i] = prefix 저장 후 prefix *= nums[i].
   • 결과적으로 ans[i]는 i 왼쪽의 곱이 된다.
2. 오→왼(suffix):
   • suffix를 1로 시작, ans[i] *= suffix 후 suffix *= nums[i].
   • 결과적으로 ans[i]는 (왼쪽 곱 × 오른쪽 곱)이 된다.

출력 배열 한 개만 사용하므로 추가 공간 O(1) 달성.

---

🔨 문제 풀이 과정

• 초기화: prefix = 1, suffix = 1, ans[] 준비
• 1차 루프(왼→오): ans[i] = i 왼쪽 곱
• 2차 루프(오→왼): ans[i] *= i 오른쪽 곱
• 반환: ans

0 처리는 별도 분기 없이 자동 처리된다. (0이 한 개면 그 위치만 비제로, 두 개 이상이면 전부 0)

---

🔨 구현코드

package leetcode;

import java.util.Arrays;

/**
 * 238. Product of Array Except Self
 * - 왼쪽/오른쪽 누적곱을 한 번씩만 사용
 * - 시간복잡도 O(n), 공간복잡도 O(1) (출력 배열 제외)
 */
public class LeSolution05 {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] ans  = new int[n];

        // 1) 왼쪽 누적곱
        int prefix = 1;
        for (int i = 0; i < n; i++) {
            ans[i] = prefix;
            prefix *= nums[i];
        }

        // 2) 오른쪽 누적곱을 곱해주기
        int suffix = 1;
        for (int i = n - 1; i >= 0; i--) {
            ans[i] *= suffix;
            suffix *= nums[i];
        }

        return ans;
    }

    public static void main(String[] args) {
        LeSolution05 sol = new LeSolution05();
        System.out.println(Arrays.toString(sol.productExceptSelf(new int[]{1, 2, 3, 4})));
        System.out.println(Arrays.toString(sol.productExceptSelf(new int[]{-1,1,0,-3,3})));
        System.out.println(Arrays.toString(sol.productExceptSelf(new int[]{0,2,3})));
        System.out.println(Arrays.toString(sol.productExceptSelf(new int[]{2,0,0,4})));
        System.out.println(Arrays.toString(sol.productExceptSelf(new int[]{-2,-3,4})));
    }
}

---

📚 풀이 보완

코드 설명

• ans[i] = prefix는 “현재 원소를 제외한 왼쪽의 곱”을 의미.
• 뒤에서 앞으로 ans[i] *= suffix는 “오른쪽의 곱”을 곱해 최종값 완성.
• prefix와 suffix는 매 스텝 현재 원소 반영 전에 곱을 사용하도록 갱신 순서가 중요.

 

• 보조 배열 두 개(left[], right[])를 사용 → 공간 O(n). 문제는 **O(1)**을 요구(출력 제외).
• prefix/suffix 갱신 순서를 바꿔 현재 원소가 포함되는 오류.
• 오버플로 걱정으로 불필요한 BigInteger 사용(문제에서 결과 32-bit 보장).

 

---

📍 Plus+

 

• 두 배열 방식:
  left[i] = 왼쪽곱, right[i] = 오른쪽곱, ans[i]=left[i]*right[i]
  • 이해는 쉽지만 공간 O(n) → 본 문제의 최적해 아님.
• 한 배열 + 두 번의 스캔(현재 코드):
  • 공간 O(1)로 최적. 면접/실전에서 가장 선호.

 

시간 복잡도와 공간 복잡도 분석

 

시간 복잡도

공간 복잡도

요약

시간 복잡도: O(n)

• 왼→오, 오→왼 각 1회 순회

공간 복잡도: O(1)

• prefix, suffix, ans[](출력 배열은 공간 복잡도 계산에서 제외)

 

• 핵심 전략: ans를 왼쪽 누적곱으로 채우고, 뒤에서 오른쪽 누적곱을 곱하는 2-pass 패턴
• 장점: 나눗셈 없이 O(n)/O(1) 달성, 0/음수 케이스도 자연 처리
• 주의: 갱신 순서(현재 원소 포함 방지), 불필요한 추가 배열 지양

 

 

---

풀이 참고 로직

• 왼→오: ans[i] = prefix; prefix *= nums[i];
• 오→왼: ans[i] *= suffix; suffix *= nums[i];