238. Product of Array Except Self

문제

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

정수가 담긴 nums 배열이 주어지고 answer 배열을 반환하는 문제. answer[i] 는 nums에서 nums[i] 를 제외한 원소들의 곱이다. 나눗셈 연산을 제외하고 O(n) 시간 복잡도로 풀 수 있어야 한다.

풀이

아이디어

나눗셈을 사용하지 못하기 때문에 전체 곱을 구해서 nums[i] 원소를 나눈 값을 answer[i]에 넣어 주는 방법을 생각했다가 바로 포기했다.

그림을 그려 보니 nums[i] 를 기준으로 왼쪽 구간과 오른쪽 구간이 1칸씩 늘어나고, 1칸씩 줄어드는 모양이라서 왼쪽 부분 (prefix)는 계속 구간을 늘려주고, 오른쪽 부분(suffix)는 계속 구간을 줄여주는 방식으로 문제를 풀었다.

코드

function productExceptSelf(nums: number[]): number[] {
    const n = nums.length;
    const answer = new Array < number > (nums.length);
 
    // answer 배열에 prefix값 설정해주기
    let prefix = 1;
    for (let idx = 0; idx < n; idx++) {
        answer[idx] = prefix;
        prefix *= nums[idx];
    }
 
    // 각 prefix에 suffix 값 누적해서 곱해주기
    let suffix = 1;
    for (let idx = n - 1; idx >= 0; idx--) {
        answer[idx] *= suffix;
        suffix *= nums[idx];
    }
 
    return answer;
}

시간 / 공간 복잡도

prefix를 구하는 과정에서 O(n) + suffix를 구하는 과정에서 O(n) 이므로 시간 복잡도는 **O(n)**이 된다.

answer 배열을 제외한 추가적인 공간을 사용하지 않으므로 공간 복잡도는 **O(1)**이다.