[Array/String][Medium] 238. Product of Array Except Self

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

Product of Array Except Self - LeetCode

 

Q. 입력 array nums가 있을때, 이 array에서 자신을 제외한 나머지 원소의 곱을 가진 array를 반환하라.

     이때 나누기연산자를 사용하지 말고, O(N)의 TC, O(1)의 SC 로 문제를 풀어라.

 

Solution. 

 우선 정순회 하면서 self 직전까지의 곱을 array에 넣는다. 

 역순회 하면서 self 직전까지의 곱을 다른 array에 넣는다. 

 self 를 기준으로 두 array를 순서대로 곱하면 self를 제외한 총 곱이 된다. 

 

Key. 앞으로, 뒤로 2 pass방식의 연산을 사용하고, 데이터를 캐시해서 재연산하는 논리 풀이방법을 아는지 확인하는 문제.

 

vector<int> productExceptSelf(vector<int>& nums)
{
    // nums의 배열값에서 해당 자신의 값을 제외한 다른값들의 곱을 반환하라.
    // O(N) time complexity and O(1) space complexity로 구현하고, 나누기 연산을 사용하지 말라.
    //
    vector<int> vRet;
    int totalMultiply = 1;
    for (int k = 0; k < nums.size(); ++k)
    {
        vRet.push_back(totalMultiply);
        totalMultiply *= nums[k];
    }

    totalMultiply = 1;
    for (int k = 0; k < nums.size(); ++k)
    {
        int idx = nums.size() - 1 - k;
        vRet[idx] = totalMultiply * vRet[idx];
        totalMultiply *= nums[idx];
    }
    return vRet;
}

 

 

 Comment : 알고리즘이라는 것이 컴퓨터의 자료구조를 활용하여, 효율적인 연산을 찾는 일련의 과정이라면, 정해진 자료구조를 효율적으로 사용하는 정형화된 방법들이 있다. 

예를 들면 sort 는 그 수행과정에 근거하여 bubble, selection, insertion, quick, merge, heap, count 등의 방법이 있다. 효율적인 sort 알고리즘은 대체로 정해져 있지만, 그럼에도, 기본적으로 상황에 기인한 취사 선택이 필요하다.(대다수의 경우 quick sort가 좋은 선택이겠지만, 정렬대상을 작은 범위로 한정할 수 있다면 count sort가 더 나은 방법일 수 있다.) 

즉, 베이스가 되는 기본들의 수행과정을 개발자가 인지한 상태에서, 상황에 맞는 패턴을 꺼내어 적용하는 것이 알고리즘 풀이 과정의 핵심이라 하겠다. 

 

그래서 이 경우는 array에서 알아야 할 여러 풀이 패턴 중 하나.