.leetcode(238. Product of Array Except Self)

문제

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

문제 풀기 전

1. 다 곱해서 하나씩 나누면 O(n)이나 나누기를 쓰지말라는 조건에 걸린다.
2. 하나빼고 다 곱하면 O(n^2)으로도 풀 수는 있다.
3. 그전까지의 곱을 모두 저장하고 있다면 계산이 좀 빠르지 않을까.

직접 푼 풀이

소요시간: 47분(21:08 ~ 21:55)

재도전하기

• 끝내 풀지 못했다.

느낀점

1. 지금까지 문제를 30개정도 풀었는데 이건 진짜 멋진 문제다. 풀이에 대한 고정관념(다 곱한것에서 하나만 나눈다)를 막으니 분명 쉬운 문제같은데 풀리지가 않았다. 아직 멀었다. 그리고 솔루션을 확인하고 나서는 진짜 멋있는 문제라고 생각했다.
2. 개념은 사실 left, right에 있었다. 꼭 다시 풀어볼 것이다.

솔루션 공부 후 추가로 푼 풀이

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] ret = new int[n];
        for (int i=0; i<n; i++) {
            ret[i] = 1;
        }

        int left=1;
        int right=1;
        for(int i=0, j=n-1; i<n-1; i++, j--) {
            left = left*nums[i];
            ret[i+1] *= left;
            right = right*nums[j];
            ret[j-1] *= right;
        }

        return ret;
    }
}

누적되는 알고리즘 접근 설명서

2021/01/09 - [알고리즘 풀이] - .leetcode(알고리즘 문제풀이 접근)