LeetCode 238. Product Of Array Except Self

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

[LeetCode - The World's Leading Online Programming Learning Platform

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

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

내 코드

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] answer = new int[nums.length];
        Map<Integer, Integer> map = new HashMap<>();

        //1. nums의 모든 요소를 map에 삽입
        for(int n : nums){
            map.put(n, map.getOrDefault(n,0)+1);
        }

        //2. nums를 순회하면서 본인에 해당하는 키의 밸류 -1한 뒤, map의 모든 엔트리값을 곱함
        for(int i=0; i<nums.length; i++){
            map.put(nums[i], map.get(nums[i])-1);
            int result=1;

            for(Map.Entry<Integer,Integer> e : map.entrySet()){

                int k = e.getKey();
                int v = e.getValue();

                if(v==0){
                    continue;
                }

                result *= (int)Math.pow(k,v);
            }

            map.put(nums[i], map.get(nums[i])+1);
            answer[i]=result;
        }

        return answer;
    }
}

문제에서 O(N)의 시간복잡도를 풀라고 했고 hash를 적용하면 되겠다 싶어 작성한 코드이다.
하지만 num을 순회할 때 map의 entrySet을 매번 순회하므로 이 또한 O(N^2)의 시간복잡도가 된다.

코드 샘플을 참고한 수정 코드

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] answer = new int[nums.length];
        int forward=1;
        int reverse=1;

        //자기자신의 모든 앞 수들을 곱합
        for(int i=0; i<nums.length; i++){
            answer[i]=forward;
            forward*=nums[i];
        }

        //자기자신의 모든 뒷 수들을 곱합
        for(int i=nums.length-1; i>=0; i--){
            answer[i]*=reverse;
            reverse*=nums[i];
        }

        return answer;
    }
}

이 문제는 자기자신을 뺀 배열의 나머지 요소들을 모두 곱하는 문제이다.
첫번째 순회에서는 ans[i]에 자기자신 이전에 누적곱하던 변수값을 그대로 저장한다. 그 다음 누적곱 변수에 자기자신을 곱한다.
따라서 한번의 순회로 자기자신의 앞수를 배열 ans의 요소로 삽입하게 된다.
두번째 순회에서는 ans[i]에 자기자신 이후에 누적곱하던 변수값을 그대로 저장한다. 그 다음 누적곱 변수에 자기자신을 곱한다.
따라서 이번 순회로 이미 자기자신의 앞수로 저장된 ans요소에 자기자신의 뒷수의 누적곱을 곱하게 되고, 결과적으로 자기자신을 제외한 모든 앞 수, 뒷 수를 곱한 값이 ans의 요소로 삽입된다.

진짜 기가막히는 아이디어이다..