> [!date] published: 2025-04-07 ## 문제 [Product of Array Except Self - LeetCode](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`)는 계속 구간을 줄여주는 방식으로 문제를 풀었다. ### 코드 ```typescript 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)**이다.