[TIL]LeetCode#238

minhyuk_ko·2022년 2월 6일
0

TIL

목록 보기
6/7

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)으로 풀이를 하여야 한다는 것이었다. 시간 복잡도를 고려하여 푼다는 것이 어려웠고, 책의 해설을 봐도 이해하기 어려웠고 직접 값을 출력해보면서 동작 하는 논리를 이해하였다.

profile
BE Developer

0개의 댓글