[Leetcode] 238. Product of Array Except Self

문제 링크 : https://leetcode.com/problems/add-two-numbers/description/

🖥️ 시작하며

문제를 요약하면, 출력되는 배열은 각 인덱스의 요소를 제외한 나머지 인덱스 요소들의 곱 이다. 그래서 가장 먼저 접근해볼 수 있는 방식은 이중 for문을 이용해 각 인덱스의 요소를 제외하고 곱을 구하는 방식이다.


class Solution:
    def calcMultiplex(self, nums: List[int]) -> int:
        sum = 1
        for i in nums:
            sum *= i

        return sum

    def productExceptSelf(self, nums: List[int]) -> List[int]:
        res = []

        for i in range(len(nums)):
            sum1 = self.calcMultiplex(nums[:i])
            sum2 = self.calcMultiplex(nums[i + 1 :])
            res.append(sum1 * sum2)

        return res

물론 당연하게도 문제에서 O(n) 방식으로 해결하라 했으니 시간 초과가 난다.

이 문제를 어떻게 O(n) 으로 해결할 수 있지? 생각하다, 그냥 공간을 조금 더 쓰면 되겠다는 아이디어가 나왔다.


# 입력 : [1, 2, 3, 4]

# 왼쪽 누적 곱 계산
for i in range(1, n):
    left[i] = left[i - 1] * nums[i - 1]
# [1, 1, 2, 6]

# 오른쪽 누적 곱 계산
for i in range(n - 2, -1, -1):
    right[i] = right[i + 1] * nums[i + 1]
# [24, 12, 4, 1]

이런 식으로,

왼쪽부터 본인의 요소를 제외한 곱

오른쪽부터 본인의 요소를 제외한 곱

을 모두 미리 계산한 다음, 이 둘을 곱하면 결과가 나오게 된다.

하나하나 뜯어보면 이해가 갈 것이다.. 결국 왼쪽부터 곱과 오른쪽부터 곱은 본인을 제외한 곱이니.

⚙️ Python


from typing import List


class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        left = [1] * n
        right = [1] * n
        res = [1] * n

        # 왼쪽 누적 곱 계산
        for i in range(1, n):
            left[i] = left[i - 1] * nums[i - 1]

        # 오른쪽 누적 곱 계산
        for i in range(n - 2, -1, -1):
            right[i] = right[i + 1] * nums[i + 1]

        # 결과 리스트 계산
        for i in range(n):
            res[i] = left[i] * right[i]

        return res


s = Solution()
print(s.productExceptSelf(nums=[1, 2, 3, 4]))

⚙️ C++


#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> productExceptSelf(vector<int> &nums) {
        vector<int> left(nums.size());
        vector<int> right(nums.size());
        vector<int> res(nums.size());

        for (int i = 1; i < nums.size(); ++i)
            left[i] = left[i - 1] * nums[i - 1];
        for (int i = nums.size() - 2; i >= 0; --i)
            right[i] = right[i + 1] * nums[i + 1];

        for (int i = 0; i < nums.size(); ++i)
            res[i] = left[i] * right[i];

        return res;
    }
};

[Leetcode] 238. Product of Array Except Self

🖥️ 시작하며

⚙️ Python

⚙️ C++

📌 소감

🔍 부록

🔍 참고문헌

댓글