Leetcode[day15] - Product of Array Except Self

Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Constraint: It's guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32 bit integer.
Note: Please solve it without division and in O(n).
Follow up:Could you solve it with constant space complexity?
(The output array does not count as extra space for the purpose of space complexity analysis.)

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

1. 알고리즘을 해결하기 위해서 생각한 방법

 

 - 우선, 최악으로 정답을 구해내는 방법을 생각해보자.

 - 가장 단순하게, 2중 for문을 활용했다.

 

2. 알고리즘 작성 중, 어려운 점

 

 - 시간 복잡도는 O(N)을 맞추기

 - 공간 복잡도는 별도로 추가하지 않기

 

3. 내가 작성한 알고리즘

 

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int answer[] = new int[nums.length];
        for(int i=0; i<nums.length; i++){
            int sum = 1;
            for(int j=0; j<nums.length; j++){
                if(i==j){
                
                }else{
                    sum *= nums[j];
                    
                }
            }
            answer[i] = sum;
        }
        return answer;
    }
}

 

4. 내가 작성한 알고리즘 결과

쥰내 느리다..

 

5. 내가 작성한 알고리즘 보완하기 (1)

 

 - 우선, 해당 문제에서는 최종적으로 시간복잡도와 공간복잡도를 요구하고 있다.

 - 시간복잡도를 증가시키기 위해서 가장 먼저 생각하게 된 것은 캐시이다.

 - map을 이용해서, 이미 계산했던 값을 집어넣어서 2번 계산을 안 하는 방법을 생각했다.

 

6. 내가 작성한 보완한 알고리즘 & 결과

 

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int answer[] = new int[nums.length];
        Map<Integer, Integer> map = new HashMap();//cache
        for(int i=0; i<nums.length; i++){
            int sum = 1;
            if(map.containsKey(nums[i])){//cache 검사
                answer[i] = map.get(nums[i]);
            }else{
                for(int j=0; j<nums.length; j++){
                    if(i==j){

                    }else{
                        sum *= nums[j];
                    }
                }
                answer[i] = sum;
                map.put(nums[i], sum);//cache put
            }
            
        }
        return answer;
    }
}

 

7. 그렇게 고민을 2시간...

 

- 시간복잡도를 O(N)으로 하기 위해서는 해당 알고리즘으로는 해결할 수 없다는 결론에 도달했다.

- 또한, 캐쉬가 필요하기 때문에 공간복잡도 또한, 높다는 것을 벗어날 수 없었다.

 

8. 나의 구세주

 

https://www.youtube.com/watch?v=EYheugF9lK8

 

9. 영상을 통해 배운 점

 

 - 해당 문제를 풀기 위해서, 우선 영상에서는 공간복잡도를 제외하고 O(N)으로 문제를 푸는 방법을 설명해줬다.

 - 왼쪽에서 오른쪽으로 이동하는 관점, 오른쪽에서 왼쪽으로 이동하는 관점으로 문제를 해결했다.

 

 

10. 학습 후, 알고리즘과 결과

 

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int answer[] = new int[nums.length];
        int prefix[] = new int[nums.length];
        int suffix[] = new int[nums.length];
        //값을 초기화 해줌
        prefix[0] = 1;
        suffix[nums.length-1] = 1;
        
        //[2,3,4,5]
        for(int i=1; i<nums.length; i++){
            prefix[i] = prefix[i-1] * nums[i-1];
            suffix[nums.length-i-1] = suffix[nums.length-i] * nums[nums.length-i];
        }
        for(int i=0; i<nums.length; i++){
            answer[i] = prefix[i] * suffix[i];
        }
        return answer;
    }
}

 

우선, 캐시와 속도는 비슷하다.

 

11. 영상의 뒷 부분 보면서, 내 아이디어화 시키기

 

 

12. 최종 알고리즘 & 결과

 

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int answer[] = new int[nums.length];
        int suffix = 1;
        answer[0] = 1;//prefix
        
        for(int i=1; i<nums.length; i++){
            answer[i] = answer[i-1] * nums[i-1]; 
        }
        
        for(int i=1; i<nums.length; i++){
            suffix *= nums[nums.length-i];
            answer[nums.length-i-1] = answer[nums.length-i-1] * suffix;
        }

        return answer;
    }
}

 

문제 : https://leetcode.com/explore/featured/card/30-day-leetcoding-challenge/530/week-3/3300/

Explore - LeetCode