238. Product of Array Except Self

#Medium #Array #Prefix Sum

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.

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]

Think

나눗셈이 가능하다면 쉽게 풀 수 있지만, 나눗셈이 불가능하다면 어떻게 해야할까?

왼쪽 곱셈과 오른쪽 곱셈을 따로 계산하여 두 값을 곱하면 된다. 누적곱(prefix product)과 누적곱(suffix product)를 따로 계산하여 두 값을 곱하면 된다. 특히 O(n)의 시간복잡도를 요구하기 때문에 for문을 두 번 돌릴 경우에는 시간 초과가 반드시 나는 문제이다. 그렇기에 한 번이 넘어가는 겹치는 반복문을 사용하면 안된다. 그렇다면 저장의 개념을 사용해야한다. p

from utils import *

def process_line(line, line_count, func):
    import traceback
    try:
        inp, oup = line.strip().split()
        inp = list(map(int, inp.split(",")))
        oup = list(map(int, oup.split(",")))

        result = func(inp)
        if result != oup:
            raise ValueError(f"WRONG : {line}")
        logger.info(f"{line_count} : {inp} --- {oup} {oup == result}")
        return line_count + 1

    except Exception:
        logger.error(traceback.format_exc())
        logger.info(f"FINISHED WITH ERROR IN {line_count}")
        return line_count


class Solution:
    from typing import List
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        answer = [1] * n
        
        for i in range(1, n):
            answer[i] = answer[i - 1] * nums[i - 1]
        
        right = 1
        for i in range(n - 1, -1, -1):
            answer[i] *= right
            right *= nums[i]
        
        return answer

problem_num = 238
logger = get_logger("DEBUG")
solution_instance = Solution()
sol(problem_num, solution_instance.productExceptSelf, logger, process_line)

[2024/12/24 11:39:35 INFO] 1 : [1, 2, 3, 4] --- [24, 12, 8, 6] True
[2024/12/24 11:39:35 INFO] 2 : [-1, 1, 0, -3, 3] --- [0, 0, 9, 0, 0] True
[2024/12/24 11:39:35 INFO] EOF