leetcode.com/problems/product-of-array-except-self/
- <파이썬 알고리즘 인터뷰>를 학습하면서 수록된 코드를 참고하였습니다. -
풀이
문제 제약 상 나눗셈을 사용할 수 없게되어 있었다. 현재 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
'Tech > Problem Solving' 카테고리의 다른 글
[리트코드(LeetCode)] 92. Reverse Linked List II - Python (1) | 2021.01.20 |
---|---|
[리트코드(LeetCode)] 24. Swap Nodes in Paris - Python (0) | 2021.01.18 |
[리트코드(LeetCode)] 15. 3Sum - Python (0) | 2021.01.12 |
[리트코드(LeetCode)] 42. Trapping Rain Water - Python (0) | 2021.01.11 |
[백준 14466] 소가 길을 건너간 이유 6 (Java) (0) | 2020.11.11 |