[알고리즘] 9 - 자신을 제외한 배열의 곱

Link for the problem

Link for the solution

개요

문제를 해결하는 것은 매우 쉽습니다. 그러나 주어진 조건은 이 문제를 매우 까다롭게 만듭니다. 솔루션이 매우 독특하기 때문에 문제를 소개하고 싶습니다.

자세한 문제

이 문제에 대한 제약 조건은 다음과 같습니다.

시간 복잡도: O(n)

공간 복잡도: O(1)

나눗셈을 사용할 수 없음

Notice that the problem will not count the returning array as an extra space.

이러한 제약 조건으로 문제를 해결하는 것은 거의 불가능해 보입니다. 특히 나눗셈을 사용하지 않고 O(1) 공간 복잡성을 달성하면 솔루션에 대해 생각하는 데 열광했습니다. 그래서 포기하고 해결책을 찾았습니다.

해결책

해결책은 내가 본 적이 없지만 이해하기 쉬운 것이 었습니다. 먼저 제품 자체 없이 제품을 얻는 방법을 생각해야 합니다. 실제로 요소의 왼쪽과 요소의 오른쪽의 곱입니다.

[ 1, 2, 3, 4 ]

ex) product without 1

- left side: 1 (does not exist)
- right side: 2*3*4 (without 1)
- left side * right side = 1 * 24 = 24


ex) product without 3

- left side: 1*2 (does not exist)
- right side: 4 (without 3)
- left side * right side = 1 * 2 * 4 = 8

다음으로 우리는 고정된 공간만을 사용하여 선형 시간에서 접두사와 접미사를 얻는 방법을 찾아야 합니다. 사실 이 부분은 우리 스스로 생각해내기가 매우 어렵습니다.

접두사를 만드는 방법은 다음과 같습니다.

1로 초기화된 변수 접두사를 설정합니다.

반환 배열에 접두사를 푸시합니다.

루프가 통과할 때 접두사를 계속 곱하십시오.

Notice that the first prefix is always going to be 1 since there is no element on the left side of the first element.

단계 후에 각 요소에 대한 접두사로 채워진 배열을 얻습니다. 이제 우리가 해야 할 일은 각 요소에 대한 접미사를 가져오고 해당 접미사를 곱하여 반환 배열을 업데이트하기만 하면 됩니다.

코드 구현

    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> res;
        int prefix = 1;
        for (int i = 0; i < nums.size(); i++)
        {
            res.push_back(prefix);
            prefix *= nums[i];
        }
        int postfix = 1;
        for (int i = nums.size()-1; i >= 0; i--)
        {
            res[i] *= postfix;
            postfix *= nums[i];
        }
        return res;
    }