238. Product of Array Except Self

1. Description

• Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
• You must write an algorithm that runs in O(n) time and without using the division operation.

2. Example

Example 1

Input: nums = [1,2,3,4] Output: [24,12,8,6]

Example 2

Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0]

3. Solution

1. 첫번째 풀이
   • Runtime: 15ms
   • 설명
     • 📌이 문제는 여러 가지 방법을 생각했었다.
       • 첫번째로 multiple이라는 함수를 만들어 start와 end를 만들어 첫번째 요소와 마지막요소를 계속해서 바꾸는 방법을 생각했다.
       • 두번째로 리스트에 있는 모든 요소를 곱한 뒤, 요소마다 그 값을 나누는 방법을 생각했다.
       • 두번째 방법으로 풀이를 진행해봤다.
     • ans리스트를 전부 0으로 채워 만든다.
     • nums[i]가 0이 아닐 때 모든 숫자의 곱을 곱한다.
     • nums[i] == 0이면 cnt를 1 더한다.
     • cnt가 2 이상이면 0이 2개 이상이라는 뜻이고, 이는 ans리스트가 전부 0이 된다는 뜻이다.
     • cnt == 1이면 0이 1개라는 뜻이고 이는 ans리스트에서 0이 들어있는 위치 빼고 전부 0이 값이 된다는 소리다.
       • 이를 이용해 nums[i] == 0이면 ans[i]에 result값을 저장한다.
     • cnt == 0 이면 nums리스트에 0이 없다는 뜻이다.
       • for문을 통해 ans[i]에 result // nums[i]값을 저장한다.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        result = 1
        ans = [0] * len(nums)
        cnt = 0
 
        for i in range(len(nums)):
            if nums[i] != 0:
                result *= nums[i]
            else:
                cnt += 1
 
        for i in range(len(nums)):
            if cnt >= 2:
                return ans
            elif cnt == 1:
                if nums[i] == 0:
                    ans[i] = result
 
            else:
                ans[i] = result // nums[i]
        return ans

2. 두번째 풀이
   • Runtime: 33ms
   • 설명
     • 

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
 
        prefix = [1] * n
        suffix = [1] * n
 
        for i in range(1,n):
            prefix[i] = prefix[i-1] * nums[i-1]
 
        for i in range(n - 2, -1, -1):
            suffix[i] = suffix[i+1] * nums[i+1]
 
        result = [prefix[i] * suffix[i] for i in range(n)]
 
        return result

• 📌Prefix Product와 Suffix Product 개념
  • 이 개념은 배열에서 특정 원소를 제외한 곱을 빠르게 게산하기 위해 사용된다.
  • 배열 nums가 주어졌을 때, 각 원소를 제외한 나머지 원소들의 곱을 효율적으로 구하는 방법이다.
• Prefix Product (왼쪽 누적 곱)
  • Prefix Product(왼쪽 곱)란 현재 원소를 기준으로 왼쪽에 있는 모든 원소의 곱을 저장하는 배열이다.

for i in range(1,n):
    prefix[i] = prefix[i-1] * nums[i-1]

• Suffix Product (오른쪽 누적 곱)
  • Suffix Product(오른쪽 곱)란 현재 원소를 기준으로 오른쪽에 있는 모든 원소의 곱을 저장하는 배열이다.

for i in range(n - 2, -1, -1):
    suffix[i] = suffix[i+1] * nums[i+1]

• 각 인덱스에서 prefix[i] * suffix[i]를 하면, nums[i]를 제외한 곱을 얻을 수 있습니다.

4. What I Learned

References

• Chat GPT