문제
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
예시
Example 1
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Example 2
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
조건
- 2 <= nums.length <= 105
- -30 <= nums[i] <= 30
- The input is generated such that answer[i] is guaranteed to fit in a 32-bit integer.
답
해당 인덱스를 기준으로 양 옆으로 숫자들을 구분해서 prefix products와 suffix products를 이용하여 해결합니다.
첫 루프에서는 prefix products만 구하고, 두 번째 루프에서 suffix products를 구해 prefix products와 곱합니다.
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int len = nums.size();
std::vector<int> products(len, 1);
int product_left = 1;
int product_right = 1;
for(int i=0; i<len; ++i) {
products[i] = product_left;
product_left *= nums[i];
}
for(int i=len-1; i>=0; --i) {
products[i] *= product_right;
product_right *= nums[i];
}
return products;
}
};
시간복잡도 : O(n)
공간복잡도 : O(1)
728x90
'CS > PS' 카테고리의 다른 글
[PS] 가장 가까운 두 수 (0) | 2025.03.21 |
---|---|
[PS] Leet | 33. 정렬된 회전 배열에서의 탐색 (0) | 2025.03.20 |
[PS] Leet | 153. 정렬된 회전배열에서의 최소값 (0) | 2025.03.20 |
[PS] Leet | 152. 최댓값을 가지는 하위 배열 - 곱셈 (0) | 2025.03.20 |
[PS] Leet | 53. 최댓값을 가지는 하위 배열 - 덧셈 (0) | 2025.03.19 |