본문 바로가기

Tech/Problem Solving

[리트코드(LeetCode)] 238. Product or Array Except Self - Python

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

 

Product of Array Except Self - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

- <파이썬 알고리즘 인터뷰>를 학습하면서 수록된 코드를 참고하였습니다. - 

 

풀이

문제 제약 상 나눗셈을 사용할 수 없게되어 있었다. 현재 index의 왼쪽 원소들의 곱과 오른쪽 원소들의 곱을 구해 두 값을 곱하는 방법을 이용하였다.

 

먼저 nums[i]의 왼쪽에 있는 값들의 곱을 output[i]에 저장한다. 현재 위치의 왼쪽의 원소들의 곱을 p라는 변수에 저장한다. nums[0]의 경우에는 가장 처음 인덱스이기 때문에 왼쪽에 존재하는 원소들이 없다. 이 경우를 위해서 p의 초기 값은 1으로 둔다. (0으로 두면 곱셈 시 모든 값이 0이 되어버리니까) p 값을 저장하고, p를 현재 인덱스의 값과 곱해 다시 저장하는 것을 반복한다.

 

이어서 nums[i]의 오른쪽 값들의 곱을 구한다. 따로 배열을 만들어서 나중에 왼쪽 값의 곱의 배열과 곱할 수도 있지만, 메모리 공간을 절약하기 위해 output에 저장된 왼쪽 값들의 곱과 바로 곱하여 값을 저장한다. 원리는 왼쪽에 있는 값들의 곱을 저장하는 것과 동일하지만, for문을 거꾸로 돌린다.

 

이렇게 계산된 값은 자연스럽게 해당 원소 값을 제외한 곱의 결과(자기 자신의 왼쪽 값들의 곱 * 오른쪽 값들의 곱)가 저장된다.

from typing import List


class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        output = []
        p = 1
        # 왼쪽 곱셈
        for i in range(len(nums)):
            output.append(p)
            p = p * nums[i]

        p = 1
        # 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈
        for i in range(len(nums) - 1, 0 - 1, -1):  # nums를 거꾸로 탐색
            output[i] = output[i] * p  # 메모리 공간 절약을 위에 output에 바로 곱하여 값을 저장
            p = p * nums[i]

        return output

www.kyobobook.co.kr/product/detailViewKor.laf?ejkGb=KOR&mallGb=KOR&barcode=9791189909178

 

파이썬 알고리즘 인터뷰 - 교보문고

세계 최고 온라인 문제 풀이 사이트인 리트코드(LeetCode)의 기출문제 풀이와 분석! 200여 개가 넘는 일러스트를 통해 알고리즘과 자료구조 이론을 한눈에 쉽게 익힐 수 있음은 물론, 파이썬으로 구

www.kyobobook.co.kr

 

반응형