> [!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)**이다.