[LeetCode]자신을 제외한 배열의 곱

문제

배열을 입력받아 output[i]가 자신을 제외한 나머지 모든 요소를 곱셈 결과가 되도록 출력하라.

예제

• 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]

코드

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        
    vector<int>res(nums.size(), 1);

	for (int i = 1; i < nums.size(); i++)
		res[i] = res[i - 1] * nums[i - 1];

	int right = 1;
	for (int i = nums.size() - 1; i >= 0; i--) {
		res[i] *= right;
		right *= nums[i];
	}
        return res;
        
    }
};

풀이

1.

 vector<int>res(nums.size(), 1);

• 값을 할당할 int형 vector res 생성. nums의 크기만큼 만들어주며, 곱셈을 위해 1로 초기화 한다.

2.

for (int i = 1; i < nums.size(); i++)
		res[i] = res[i - 1] * nums[i - 1];
	

• res의 1번 인덱스부터 값을 넣어주는데, res[i - 1]은 nums의 0번째 인덱스부터 i - 2 번째 인덱스 모두 곱한 값이 되며 여기에 nums[i - 1] 까지 곱함으로써 자기 자신을 제외한 왼쪽의 모든 곱한 값을 가지게 된다.

3.

int right = 1;
	for (int i = nums.size() - 1; i >= 0; i--)
    {
		res[i] *= right;
		right *= nums[i];
	}

• 2번 풀이에서 곱하지 않은 현재 인덱스의 오른쪽 값을 곱해줄 차례이다. right 변수에 현재의 인덱스의 모든 오른쪽 값들의 곱을 담아서, 현재의 인덱스 값에 다시 곱해준다.

결과

Runtime 30 ms / Memory 24.1 MB
https://leetcode.com/problems/product-of-array-except-self/submissions/887962778/

---

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