[ArraysHashing][Medium] 238. Product of Array Except Self

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

 

정수 배열이 주어 질 때, 자신을 제외한 곱을 구하는 알고리즘을 작성하라. 

이때 O(n)의 TC에 추가 메모리를 사용하지 말라. 

이때 반환할 버퍼는 추가 메모리로 간주하지 않는다. 

 

자주 나오는 패턴의 문제. 

제한이 없을 때 매우 간단한 문제. 

 

O(n)의 TC 제한이 있으므로, 2중 loop는 허용되지 않는다. 

O(1)의 space complexity 만을 가져야 하므로, 반환할 버퍼에 임시 데이터를 쓴다.

 

vector<int> productExceptSelf(vector<int>& nums) 
{        
    vector<int> vRet;
    vRet.resize(nums.size(), 1);

    int cur = 1;
    for (auto k = 0; k < nums.size(); ++k)
    {
        vRet[k] = cur;
        cur *= nums[k];
    }

    cur = 1;
    for (int k = nums.size() - 1; k >= 0; --k)
    {
        vRet[k] = cur * vRet[k];
        cur *= nums[k];
    }
    return vRet;
}

 

알고리즘 풀이 능력이 연습으로 개선될 수 있다는 걸 알려주는 문제 중의 하나. 

 

결과.