[TIL]LeetCode#238

238. Product of Array Except self

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

입력

[1, 2, 3, 4]

출력

[24, 12, 8, 6]

풀이

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
    	result = []
        # 왼쪽으로 곱셈 [1, 1 * (1), 1 * (1 * 2), 1 * (1 * 2 * 3) ]
        p = 1
        for i in range(len(nums)):
        	result.append(p)
            p *= nums[i]
        # 오른쪽으로 곱셈 [1 * (4 * 3 * 2), 1 * (1) * (4 * 3), 1 * (1 * 2) * (3), 1 * (1 * 2 * 3) * (1)]
       	p = 1
        for i in range(len(nums)-1, -1, -1):
        	result[i] *= p
            p *= nums[i]

로직

[1, 1, 1, 1] 에서 오른쪽으로 한칸씩 밀린 배열을 곱한다. 그리고 그 배열에 기존배열을 왼쪽으로 한칸씩 밀고 요소들을 곱한다.

느낀점

그냥 for문을 중복시키면 쉽게 결과값을 구할 수 있지만 문제에서 강조하는 것은 복잡도를 O(n)으로 풀이를 하여야 한다는 것이었다. 시간 복잡도를 고려하여 푼다는 것이 어려웠고, 책의 해설을 봐도 이해하기 어려웠고 직접 값을 출력해보면서 동작 하는 논리를 이해하였다.