[Prefix Sums] 238. Product of Array Except Self ☆

238. Product of Array Except Self

 

 

문제 풀이

이 문제는 주어진 배열 nums에서, 각 요소를 제외한 나머지 요소들의 곱을 계산하여 결과 배열을 반환하는 문제입니다. 나눗셈 없이, 시간 복잡도 O(n) 로 해결해야 합니다.

---

문제 조건

1. 각 answer[i] 는 배열 nums의 i 번째 요소를 제외한 나머지 요소들의 곱입니다.
2. 나눗셈 사용 금지: 단순히 배열 전체 곱을 구한 뒤 각 요소로 나누는 방식은 사용할 수 없습니다.
3. 시간 복잡도는 O(n), 공간 복잡도는 O(1) 추가 공간(결과 배열은 제외).

풀이 방법

1. 아이디어

배열의 곱을 효율적으로 계산하려면 다음과 같은 접근법을 사용할 수 있습니다:

• 왼쪽 누적 곱 (prefix product): 각 요소 iii에서, 왼쪽에 있는 모든 요소들의 곱.
• 오른쪽 누적 곱 (suffix product): 각 요소 iii에서, 오른쪽에 있는 모든 요소들의 곱.
• 결과는 왼쪽 곱 × 오른쪽 곱으로 계산할 수 있습니다.

2. 구현 과정

1. 배열의 크기를 nnn이라고 할 때:
   • 왼쪽 곱 배열 left : left[i] 는 nums[i] 왼쪽의 곱.
   • 오른쪽 곱 배열 right : right[i] 는 nums[i] 오른쪽의 곱.
2. 최종 결과 answer[i] = left[i] × right[i] .
3. 공간 최적화: left 와 right 배열 대신 하나의 배열 answer와 추가 변수 두 개로 처리.

https://youtu.be/V_De_bhXKzc?si=llCLzgmLGkh_ZsgF

 

최종 코드

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        lenN = len(nums)

        # 왼쪽 곱과 오른쪽 곱을 저장할 배열 초기화 (모두 1로 시작)
        prefixMul = [1] * lenN       # prefixMul[i] = nums[0] * ... * nums[i-1]
        postfixMul = [1] * lenN      # postfixMul[i] = nums[i+1] * ... * nums[-1]
        res = [1] * lenN             # 최종 결과 배열

        # 왼쪽 곱 계산
        for i in range(1, lenN):
            prefixMul[i] = nums[i-1] * prefixMul[i-1]
            # i번째 위치에 i-1까지의 곱 저장

        # 오른쪽 곱 계산 (역순)
        for i in range(lenN - 2, -1, -1):
            postfixMul[i] = nums[i+1] * postfixMul[i+1]
            # i번째 위치에 i+1부터 끝까지의 곱 저장

        # 결과 배열 계산: 왼쪽 곱 * 오른쪽 곱
        for i in range(lenN):
            res[i] = prefixMul[i] * postfixMul[i]

        return res

 

최적화 코드 (1)

 

이건 앞서 짰던 prefixMul, postfixMul, res 버전에서
결과 배열 res에 곧바로 값을 누적하면서 최적화한 방식이에요.

---

✅ 이 코드의 핵심은?

• res[i]에 바로 prefix 곱을 저장
• 그리고 **postfix를 구하면서 res[i] *= postfix[i]**로 오른쪽 곱도 곱해줌
  → 결국 res[i] = prefix[i] * postfix[i]가 됨

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        lenN = len(nums)

        prefixMul = [1] * lenN         # 왼쪽 곱 배열
        postfixMul = [1] * lenN        # 오른쪽 곱 배열
        res = [1] * lenN               # 결과 배열

        # 1. 왼쪽 곱 계산 + 결과 배열에 저장
        for i in range(1, lenN):
            prefixMul[i] = nums[i - 1] * prefixMul[i - 1]
            res[i] = prefixMul[i]      # res에 prefix값 미리 저장

        # 2. 오른쪽 곱 계산 + 결과 배열에 곱해서 완성
        for i in range(lenN - 2, -1, -1):
            postfixMul[i] = nums[i + 1] * postfixMul[i + 1]
            res[i] *= postfixMul[i]    # res에 postfix 곱해서 최종 결과 완성

        return res

 

최적화 코드 (2)

✅ 공간 최적화 하고 싶다면?

이제 prefixMul, postfixMul 배열은 필요 없고,
res 하나에 prefix 누적 → postfix는 변수로만 누적하면 됩니다!

🔽 최종 최적화 버전 (공간 O(1) - 결과 배열 제외):

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        lenN = len(nums)
        res = [1] * lenN

        # 왼쪽 곱 누적
        prefix = 1
        for i in range(lenN):
            res[i] = prefix
            prefix *= nums[i]

        # 오른쪽 곱 누적하면서 res에 곱함
        postfix = 1
        for i in range(lenN - 1, -1, -1):
            res[i] *= postfix
            postfix *= nums[i]

        return res

 

이 최적화 버전도 같은 로직인데, 메모리를 더 아껴요.
면접에서도 이 순서로 설명하면 좋아요:

1. prefix-postfix 배열 2개 버전
2. res에 하나로 합친 버전
3. 최종 최적화 O(1) 버전