LeetCode-238
Product of Array Except Self : Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
note : Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)
Answer
:::python
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
out = []
p = 1
for i in range(0, len(nums)):
out.append(p)
p = p*nums[i]
p = 1
for i in range(len(nums)-1, 0-1, -1):
out[i] = out[i]*p
p = p * nums[i]
return out
Result : 221ms Memory: 21.2mb
Leetcode Problem "Product of Array Except Self" Solution
이 문제는 주어진 배열에서 자신을 제외한 모든 요소들의 곱을 계산하는 문제입니다. 추가적인 배열을 사용하지 않고 O(n) 시간복잡도 내에 풀어야 합니다.
우선, 모든 요소들의 곱을 구하기 위해서는 배열 전체의 곱을 계산한 뒤, 각 요소마다 전체 곱에서 자신의 값을 나눠줘야 합니다. 하지만 이 방법은 0이 하나라도 있는 경우 오류가 발생합니다.
따라서, 각 요소를 제외한 왼쪽 요소들의 곱과 오른쪽 요소들의 곱을 구해야 합니다. 이를 위해서는 두 개의 배열을 사용합니다. 첫 번째 배열은 각 요소의 왼쪽 요소들의 곱을, 두 번째 배열은 각 요소의 오른쪽 요소들의 곱을 저장합니다.
그리고 나서 각 요소의 왼쪽 요소들의 곱과 오른쪽 요소들의 곱을 곱하면, 자신을 제외한 모든 요소들의 곱이 됩니다.
이렇게 해서 추가적인 배열 없이 O(n) 시간복잡도 내에 문제를 풀 수 있습니다.
User Python Code Evaluation
위 코드는 올바르게 구현되어 있습니다. 각 요소의 왼쪽 요소들의 곱을 구하는 반복문과 오른쪽 요소들의 곱을 구하는 반복문으로 구성되어 있고, 추가적인 배열을 사용하지 않고 O(n) 시간복잡도 내에 문제를 풀었습니다. 따라서, 이 코드는 정확성과 효율성 모두를 충족시키는 좋은 코드입니다.
'One step' 카테고리의 다른 글
[leetcode 234] Palindrom Linked List (0) | 2023.03.11 |
---|---|
[leetcode-121] Best Time to Buy and Sell Stock (0) | 2023.03.09 |
[leetcode-561] Array Partition (0) | 2023.03.07 |
[leetcode-15] Three Sum (0) | 2023.03.06 |
[leetcode-42] Trapping Rain Water (0) | 2023.03.05 |