[파이썬 알고리즘 인터뷰] 10. 자기자신을 제외한 배열의 곱

 

github.com/onlybooks/algorithm-interview

 

 

1. 문제

leetcode 238. Product of Array Except Self

정수형 배열 nums가 입력되면 answer[i]가 nums[i]를 제외한 nums의 모든 원소의 곱이 되는 배열 answer을 리턴하시오.

 

2. 내 풀이

 answer[i + 1] = answer[i] * (nums[i +1]/nums[i])이 성립하는 것을 이용해서 문제를 풀었다. 

def productExceptSelf(self, nums: List[int]) -> List[int]:
    results = []
    tmp = 1

    # 0이 등장할 때
    if 0 in nums:
        results = [0 for i in nums]
        zero = nums.index(0)
        nums.pop(zero)
        for n in nums:
             tmp *= n
        results[zero] = tmp
        return results

	#첫번째 답 구하기
    for i in range(1, len(nums)):
        tmp *= nums[i]
    results.append(tmp)

	#나머지 답 구하기
    for i in range(len(nums) - 1):
        results.append(int(results[i] * (nums[i]/(nums[i + 1]))))

    return results

 

3. 왼쪽과 오른쪽의 곱을 차례로 구하기

책에서는 각 배열을 기준으로 왼쪽의 곱, 오른쪽의 곱을 따로 구해서 문제를 해결했다. 먼저 왼쪽의 곱을 차례로 계산해서 배열에 저장한다. 그리고 반대쪽부터 오른쪽의 곱을  p에 저장하고 이미 저장되어 있는 왼쪽의 곱 * p를 통해 구하고자 하는 자기자신을 제외한 곱을 구한다.

def productExceptSelf(self, nums: List[int]) -> List[int]:
    out = []
    p = 1
    # 왼쪽 곱셈
    for i in range(0, len(nums)):
        out.append(p)
        p = p * nums[i]
    p = 1
    # 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈
    for i in range(len(nums) - 1, 0 - 1, -1):
        out[i] = out[i] * p
        p = p * nums[i]
    return out

이번 문제를 풀면서 구간합(Prefix Sum)에 대해서 알게 되었다. 말 그대로 전체 배열에서 특정 구간의 합을 여러번 구해야 할 때 시간복잡도를 줄이기 위해서 사용하는 방법이다. 부분합 배열은 원래 배열에서 해당 원소까지의 합을 저장한다.

원래 배열 arr	1	2	1	3	4
부분합 배열 sum	1	3	4	7	11

이를 통해 a부터 b까지의 합을 구할때 sum[b] - sum[a - 1]로 모든 원소의 합을 일일히 계산하지 않고 간단하게 구할 수 있다.