[LeetCode][C++/Python] 238번: Product of Array Except Self (262)

 

생각의 흐름

사실 문제를 보자마자 든 생각은 전체 수를 다 곱한다음, 해당 자리의 수로 나누는 방식이다.

아마 나같은 일반인이라면 당연히 나누는 방식을 생각했을 것 이다...

 

하지만 문제 제약 조거을 보면.... "나누기 금지"....

 

따라서 좀더 생각을 하게 되었다. 일단 문제는 O(N)안에 해결 가능해야 한다는 점이다.

일단 투포인터 비슷한 방식으로 해야 하지 않을까? 란 생각이 먼저 들었다. O(N)안에 가능해야 하니 말이다!

 

어떤 수 하나를 생각해보면, 그 수의 index의 양옆 => (0 ~ index - 1), (index + 1 ~ N)의 수를 전부 곱해야 한다.

그럼 우선 배열을 순회하면서 왼쪽의 곱들만 구하고, 그 다음 오른쪽으 곱들을 곱하면 어떨까?

 

다음 문제의 예시를 생각해보자!

[1,2,3,4]

자기 자리의 왼쪽만 전부 곱하는 경우
[1,1,2,6]

다시 자기 자리의 오른쪽만 전부 곱하는 경우
[24,12,8,6]

반복문은 2번 돌기 때문에 O(2N)정도로 해결 가능할 것이다!

 

나의 코드

1. Python

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        res = []
        temp = 1
        for i in range(len(nums)):
            res.append(temp)
            temp *= nums[i]

        temp = 1
        for i in range(len(nums) - 1, -1, -1):
            res[i] *= temp
            temp *= nums[i]
        
        return res

 

2. C++

C++은 다른 분의 풀이를 보고 조금은 다르게(?) 풀어보았다!

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());

        partial_sum(nums.begin(), nums.end(), left.begin(), multiplies<int>());
        partial_sum(nums.rbegin(), nums.rend(), right.rbegin(), multiplies<int>());
        for(int i = 0; i < size(nums); i++) {
            res[i] = (i ? left[i-1] : 1) * (i+1 < size(nums) ? right[i+1] : 1);
        }
        return res;
    }
};

핵심은 pertial_sum()을 이용하는 점 이다. 양옆의 모든 수를 곱한다는 점은 동일하다!