LeetCode - The World's Leading Online Programming Learning Platform

문제 풀이 아이디어

문제의 제약

문제의 제약 중에 “You must write an algorithm that runs in O(n) time and without using the division operation.”라는 문장이 있다. 시간복잡도가 O(n)이어야 하고 “나눗셈”을 사용하면 안된다는 뜻이다. 나는 문제를 보자마자 일단 다 곱한 다음에 nums[i]로 나누어서 구하려고 했는데 그 방법을 사용할 수 없게 되었다.

투 포인터 비슷한 접근

O(N^2)으로 풀어야만 할 것 같은 문제를 O(N)으로 풀 수 있는 방법에는 여러가지가 있지만 가장 대표적인 방법은 요즘 포스팅에서 많이 사용했던 투포인터 방식이다. 투포인터는 수직선이 있을 때 왼쪽 끝, 그리고 오른쪽 끝은 기준으로 가운데로 좁혀가면서 문제를 해결하는 방식이다.

하지만 여기서 사용하는 투 포인터는 살짝 다르다. 물론 왼쪽 끝, 오른쪽 끝에서 시작이라는 컨셉은 비슷하지만 중간에 만나는 것이 아니라 일단 쭉 끝까지 곱해서 구한다.

각각의 배열은 left, right라고 하자. left 배열의 i번째 element는 nums[0] ~ nums[i - 1]까지 곱한 값이 된다. 그리고 right 배열의 i번째 element는 nums[nums.count - 1] ~ nums[i + 1]까지 곱한 값이 된다.

그렇다면 정답 배열의 i 번째 element는 left[i] * right[i]로 쉽게 구할 수 있다.

코드

class Solution {
    func productExceptSelf(_ nums: [Int]) -> [Int] {
        
        var left = Array(repeating: 1, count: nums.count)
        var right = Array(repeating: 1, count: nums.count)
        
        // left의 i는 nums[0] ~ nums[i - 1]까지 곱한 값
        for i in 1..<nums.count {
            left[i] = left[i - 1] * nums[i - 1]
        }
        
        // right의 i는 nums[nums.count - 1] ~ nums[i + 1]까지 곱한 값
        for i in (0..<(nums.count - 1)).reversed() {
            right[i] = right[i + 1] * nums[i + 1]
        }
        
        var ans = [Int]()
        
        // ans의 i는 결과적으로 nums[i]빼고 모두 곱한 값이 된다.
        for i in 0..<nums.count {
            ans.append(left[i] * right[i])
        }
        
        return ans
    }
}