238. 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.

 

[TC]

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Constraints:

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

 

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

 

[접근]

실패코드의 접근 방법은 조합을 사용해서 총 nums 에서 나를 제외한 나머지 수를 뽑아서 곱하는 것으로 구상.

결과, TimeLimit 으로 InAccepted 가 나왔다. 이외에도 다른 방법을 구안하려 했으나, 대안이 안나와서 Solution 에 있는 방법을 참고하여 해결

 

성공코드 접근 방법은 좌측에서 우측으로 곱한 후, 우측에서 변수를 누적곱해오면서 연산하는 방법이라고 밖에 설명이 불가능 할것 같다. 자세한 내용을 코드 참조.

 

[실패 코드] C++

class Solution {
public: vector<int> input;
public: vector<int> result;// = new vector<int>();
public: int k;
public: int n;

public: stack<int> st;

public:
    vector<int> productExceptSelf(vector<int>& nums) {
        input = nums;
        n = nums.size();
        k = nums.size()-1;

        Combi(-1,result);

        vector<int> res;

        for(int i = 0 ; i < st.size();)
        {
            res.push_back(st.top());
            st.pop();
        }

        return res;
    }

public:
    void Combi(int start, vector<int> b)
    {
        if(b.size() == k)
        {
            int value = 1;
            for (int i = 0; i < b.size(); ++i)
                value *= b[i];

            st.push(value);
        }

        for(int i = start+1; i < n; i++ )
        {
            b.push_back(input[i]);
            Combi(i,b);
            b.pop_back();
        }
    }
};

 

[성공 코드] C#

public class Solution {
    public int[] ProductExceptSelf(int[] nums) {
        int[] ret = new int[nums.Length]; 
        // 길이만큼 생성

        ret[0] = 1; // 가장 앞은 1로 고정

        for(int i = 1; i < ret.Length; ++i)
            ret[i] = ret[i-1] * nums[i-1];
        // 내 앞수들 곱한거를 먼저 넣기

        int EndValue = 1;
        // 오른쪽 끝에서 도입할 변수

        for(int i = ret.Length-1; i >= 0; --i)
        {
            ret[i] *= EndValue;
            EndValue *= nums[i];
        }


        return ret;
    }
}

 

[성공 결과]

[실패 결과]

[후기]

문제를 보았을때, 가장먼저 생각한 부분은 단순히 나를 제외한 숫자를 뽑은 후 곱연산으로 결과를 리턴시켜주면 된다고 생각했다. 그러나, 이 방법은 지금에와서는 시간복잡도도 많이 걸리지만, 단순 TC 만 패스할 수 있는 답이라고 생각이 된다.

참고했던 솔루션을 보니 DP, 브루탈 포스? 등등을 작성해 놓은것을 볼 수 있었는데, 이 내용들은 더욱 심화적으로 공부할 필요가 있다고 생각한다.

 

어려운 문제도 더 풀 수 있도록 노력해야겠다.

이 문제만 이틀을 잡아먹은게 너무 아쉽다..