[배열] 11 자신을 제외한 배열의 곱(Product of Array Except Self)

<LeetCode 문제>

https://leetcode.com/problems/product-of-array-except-self/

Product of Array Except Self - LeetCode

배열을 입력받아 output[i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력하는 문제입니다.

이때 나눗셈을 하지 않고 O(N)에 풀이해야 되는 점이 핵심입니다.

<풀이>

처음에 머리에 든 생각은 미리 전체 곱셈 값을 구해놓고 각 항목별로 자기 자신을 나눠서 풀이하는 방법이었는데, 이는 제약조건에 걸려서 불가능합니다.

따라서, 자기 자신을 제외하고 왼쪽의 곱셈결과와 오른쪽의 곱셈 결과를 곱해야 합니다. 이러한 발상을 생각하는게 매우 어려운 문제였습니다.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        out = []
        p = 1
        
        #[1,2,3,4]일때
        
        #왼쪽부터 곱셈해나가기
        #자기자신을 제외한 왼쪽의 곱셈결과 p는 [1,1,2,6]
        for i in range(0,len(nums)): #i는 0,1,2,3
            out.append(p)
            p = p * nums[i]
        
        p=1
        
        #오른쪽부터 곱셈해나가기
        #자기자신을 제외한 오른쪽의 곱셈결과 p는 [1,4,12,24]
        for i in range(len(nums)-1,0-1,-1): #i는 3,2,1,0
            out[i] = out[i] * p
            p = p * nums[i]
        
        return out

 

<학습내용>

1. 인덱스 거꾸로 참조할때 range(len(nums)-1,0-1,-1). 두번째 인자가 -1인 점 주의
reversed(range(len(nums))를 해도 된다.

<학습이 필요한 내용>

1. python range 다양한 사용법

 

https://github.com/HoYoungChun/Algorithm_PS/blob/master/Python_Study/07_array/LC_238.py

GitHub - HoYoungChun/Algorithm_PS: Baekjoon Online Judge, Programmers, LeetCode problem solving by Python, C++