[Leet Code] Product of Array Except Self (Kotlin)

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

Product of Array Except Self - LeetCode

유형

1. 구현

2. 누적곱(?)

풀이

방법1) 나눗셈을 이용한 풀이

1. 모든 원소(nums)를 곱한 다음, 전체 곱에서 자신을 나눈 값을 저장한다. -> answer[i] = totalProduct / nums[i]

2. nums[i]가 0일 땐 나눌 수 없으니, 곱할 때 0은 제외한다.

3. 곰곰이 생각해보면 nums에 0이 2개 이상이면, answer[i]는 모두 0이다. 

4. 따라서, (1) 0이 없을 때, (2) 1개 일 때, (3) 2개 이상일 때, 3가지 케이스로 나눌 수 있다.

방법2) 누적 알고리즘을 이용한 풀이

문제에서 나눗셈을 이용하지 말라고 한다. 누적곱(?)을 사용하자.

그림으로 왜 누적곱을 사용하는지 알아보자.

알아봤다!

 

i번째 정답 원소 = (왼쪽에서 오른쪽 방향 누적 곱) + (자기 자신) + (오른쪽에서 왼쪽 방향 누적 곱)

--> answer[i] = leftPrefix[i - 1] + nums[i] + rightPrefix[i + 1]

 

나눗셈을 사용하지 않으면서 O(n)으로 해결할 수 있다.

코드1 (나눗셈 사용)

class Solution {
    fun productExceptSelf(nums: IntArray): IntArray {
        var indexOfZero = - // 원소 0의 인덱스
        var product = 1     // 0을 제외한 모든 곱
        val answer = IntArray(nums.size)
        
        for (i in nums.indices) {
            // 0이 2개 이상 -> 모든 값이 0이 되기 때문에 stop
            if (nums[i] == 0 && indexOfZero != -1) {
                product = 0
                break
            } else if (nums[i] == 0 && indexOfZero == -1) { // 0을 처음 발견했을 때
                indexOfZero = i
                continue
            }
            
            product *= nums[i]
        }
        
        // 0이 하나라면, answer[indexOfZero] = 나머지 원소의 곱, 나머지는 0
        if (product != 0 && indexOfZero != -1) {
            answer[indexOfZero] = product
        } 
        // 0이 없을 때
        else if (indexOfZero == -1) {
            for (i in answer.indices) {
                answer[i] = product / nums[i]
            }
        }
        
        return answer
    }
}

코드2 (누적 알고리즘)

/**
 * answer[i] = 왼쪽누적곱[i-1] * 오른쪽누적곱[i+1]
 */
class Solution {
    fun productExceptSelf(nums: IntArray): IntArray {
        val answer = IntArray(nums.size)
        val leftPreProducts = IntArray(nums.size)
        val rightPreProducts = IntArray(nums.size)
        
        leftPreProducts[0] = nums[0]
        rightPreProducts[nums.lastIndex] = nums.last()
        
        // 오른쪽 방향으로 누적곱
        for (i in 1 until nums.size) {
            leftPreProducts[i] = leftPreProducts[i-1] * nums[i]
        }
        // 끝에서 왼쪽 방향으로 누적곱
        for (i in nums.lastIndex - 1 downTo 0) {
            rightPreProducts[i] = rightPreProducts[i + 1] * nums[i]
        }
        
        for (i in 1 until answer.lastIndex) {
            answer[i] = leftPreProducts[i - 1] * rightPreProducts[i + 1]
        }
        answer[0] = rightPreProducts[1]
        answer[answer.lastIndex] = leftPreProducts[answer.lastIndex - 1]
        
        return answer
    }
}