[ leetcode 문제풀이 ] Product of Array Except Self

https://leetcode.com/problems/product-of-array-except-self/

Product of Array Except Self - LeetCode

(Product of Array Except Self 문제는 위 링크에서 풀어보실 수 있습니다.)

 

 

 

< Product of Array Except Self 문제 설명 >

 

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].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.

 

주어진 정수 배열 num에 대해 answer[i]가 nums[i]를 제외한 모든 원소의 곱을 나타내는 배열 answer을 리턴하여라.

nums에 대한 어떠한 prefix, suffix product는 32비트 정수 내의 숫자임이 보장되어 있다.

몫 연산자를 사용하지 않고 O(n) 시간을 만족하는 알고리즘을 작성하여라.

 

다음 두 가지 출력 예시가 주어졌다.

 

 

주어진 제한 조건은 2 ≤ nums.length ≤ 10^5 , -30 ≤ nums[i] ≤ 30 이다.

Follow up question으로는 O(1)의 추가 공간복잡도로 문제를 풀 수 있겠는가? (output 배열은 추가 공간복잡도에 포함되지 않음) 이다.

 

 

 

---

< Product of Array Except Self 문제 접근 - 기본 >

 

몫 연산자를 사용할 수 없으므로 전체에 대한 곱을 계산하고 각각의 원소로 나누는 방식은 사용할 수 없다. 그렇다고 모든 index마다 필요한 원소를 다 곱하고 있으면 O(n^2)의 시간복잡도를 갖게 된다. 따라서, 미리 곱셈을 해둬야 함은 명확하다.

 

그럼 미리 곱셈을 어떻게 해둬야 하며, 어떻게 써먹어야 할까?

i번째 index에 대해서 answer[i]를 구하려고 한다고 생각해보자. 그러면 nums[i]를 제외한 원소들의 곱을 알아야 하며, 이를 i를 기준으로 두 부분으로 나누면 nums[0 ... i-1] 의 곱과 nums[i+1 ... nums.size()-1] 의 곱을 알아야 한다고 할 수 있다. 

 

각각은 nums에 대해 product of prefix, suffix 이므로 간단하게 구할 수 있다. 이 원리로 알고리즘을 구성하면 다음과 같다. (Cpp 사용)

 

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> prefix_prod(n);
    vector<int> suffix_prod(n);
        
    prefix_prod[0] = 1;
    suffix_prod[n-1] = 1;
    for(int i=1;i<n;i++){
        prefix_prod[i] = prefix_prod[i-1]*nums[i-1];
        suffix_prod[n-1-i] = suffix_prod[n-i]*nums[n-i];
    }
        
    vector<int> ans(n);
    for(int i=0;i<n;i++)
        ans[i] = prefix_prod[i]*suffix_prod2[i];
       
    return ans;
}

 

이렇게 하면, product of prefix, suffix of nums를 구하는 과정에서 O(n), ans[i] 값을 구하는 과정에서 O(n)의 시간복잡도를 가지며 몫 연산을 사용하지 않았으므로 주어진 제한 조건에 모두 부합한다.

 

한편, follow up question에서 요구하는 O(1)의 추가 공간복잡도 조건은 만족하지 못하였다. (prefix_prod, suffix_prod : extra space complexity O(n))

 

 

O(1)의 추가 공간복잡도를 갖는다는 것은 위 코드에서 ans vector을 선언한 것을 제외한 prefix_prod, suffix_prod과 같은 것이 없어야 한다는 것이다. 물론, 이건 크게 어렵지 않다. prefix_prod 나 suffix_prod 중 하나를 ans vector로 직접 사용하고 나머지 하나의 역할은 nums 배열에 적용하면 되기 때문이다. 코드로 구현하면 다음과 같다. (Cpp 사용)

 

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> ans(n,1);
    for(int i=1;i<n;i++)
        ans[i] = ans[i-1]*nums[i-1];
    for(int i=n-2;i>-1;i--){
        nums[i] = nums[i]*nums[i+1];
        ans[i] = ans[i]*nums[i+1];
    }
    return ans;
}

 

출력하고자 하는 ans 배열을 prefix_prod의 역할로 사용하였고, nums 배열을 suffix_prod의 역할로 사용하였다. 

이로써 Follow up question에서 요구하는 memory 조건도 만족시켰다.