Daily LeetCode Challenge - 238. Product of Array Except Self

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

오늘 문제는 nums 배열이 주어졌을때, 각자의 원소에서 각 원소를 제외한 나머지를 곱한 숫자를 넣고 반환하는 문제였다.

이 문제를 제한사항을 추가해서 풀었는데, 나누기 연산을 쓰지 않고, 시간복잡도를 O(N) 그리고 공간복잡도를 O(1) 로 해서 풀어내었다.
먼저, 문제 풀이에 필요한 개념을 짚고 넘어가야하는데, 각자의 원소에서 해당 원소를 제외한 곱을 구하려면, 해당 원소의 앞의 원소의 곱을 알아내고, 해당 원소의 뒤의 곱을 알아낸뒤에 두 수를 곱해주면 되었다.

처음 nums 배열을 탐색할때, result 라는 nums 와 크기가 똑같은 배열을 선언해두고, nums 를 처음부터 탐색하면서 result 의 각 자리에 prefix 를 곱하고, prefix 에 nums의 각 자리를 곱해주었다.

그렇게 저장된 result 배열을 들고, 다시한번 suffix 와 nums 배열을 거꾸로 탐색하면서 곱해주면 result 에는 정답이 들어가게 된다.

class Solution {
    fun productExceptSelf(nums: IntArray): IntArray {

        val result = IntArray(nums.size) { 1 }

        var prefix = 1
        for(i in 0 until nums.size) {
            result[i] *= prefix
            prefix *= nums[i]
        }

        var suffix = 1
        for(i in nums.size - 1 downTo 0) {
            result[i] *= suffix
            suffix *= nums[i]
        }

        return result
    }
}

위 문제의 시간복잡도는 O(N) 이 되고, 공간복잡도는 정답을 위한 배열을 제외하면, 상수만 사용하였으므로 O(1) 이 된다.