LeetCode #238 Product of Array Except Self

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

LeetCode #238 Product of Array Except Self

문제 풀이

그냥 해결하면 쉬워보이지만 follow up 질문에 나눗셈을 사용하지 않고 시간복잡고 n으로 해결할 수 있는지 여부를 묻는다. 즉, 면접이라면 추가질문이란 뜻이다. 일단 처음과 끝지점은 자기 자신을 빼고 곱하면 되기 때문에 거꾸로 생각해보자. 오른쪽 지점은 왼쪽에서 시작해서 자신의 위치 직전까지 곱하면 되고 왼쪽 지점은 오른쪽에서 시작해서 자신의 위치 직전까지 곱하면 된다. 이걸 반복문으로 구현해서 응용하면 될 것 같다.

python 코드

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        sol = []
        p = 1 # 곱할 값
        for i in range(len(nums)): # 각 원소에 대해
            sol.append(p) # p를 더함(오른쪽 원소를 위해 왼쪽으로 당기기 위함)
            p *= nums[i] # p에 왼쪽 원소부터 차례로 곱함
        p = 1 # 곱할 값 초기화
        for i in range(len(nums) - 1, -1, -1): # 각 원소에 대해 역순
            sol[i] *= p # 이로써 자기 자신을 제외한 값을 곱하게 됨
            p *= nums[i] # 오른족 원소부터 곱하기
        return sol