매일 LeetCode 풀기 | Product of Array Except Self

 

Product of Array Except Self

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]
 
Constraints:
2 <= nums.length <= 105-30 <= nums[i] <= 30The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

 

처음 이 문제를 풀려고 했을 때, 전체 곱을 곱한 다음에 배열을 순회하면서 나눗셈을 하려고 했다. 그런데 여기서 나눗셈을 쓰지 말라고 하여.. 길을 잃게 되었고 결국은 혼자 힘으로 풀지 못했다. 

 

이 문제를 푸는 중요 접근 방식은 투포인터와 비슷한 접근 방식이었다. 

 

class Solution {
    func productExceptSelf(_ nums: [Int]) -> [Int] {
        let n = nums.count
        var result = [Int](repeating: 1, count: n)

        var leftProduct = 1
        for i in 0..<n {
            result[i] *= leftProduct
            leftProduct *= nums[i]
        }

        var rightProduct = 1
        for i in (0..<n).reversed() {
            result[i] *= rightProduct
            rightProduct *= nums[i]
        }


        return result
    }
}

 

접근 방식 
1. result 배열을 만들어둔다. 
2. 왼쪽에서 오른쪽의 누적곱을 구한다. 
3. 오른쪽에서 왼쪽의 누적곱을 구한다. 
4. 최종 결과를 반환한다.