코틀린 코딩테스트 강좌, 구간 곱 구하기

문제 설명

주어진 숫자 배열의 구간에 해당하는 곱을 구하는 문제입니다.
예를 들어, 숫자 배열 [2, 3, 4, 5]가 주어졌을 때,
구간 [1, 3]에 해당하는 곱은 3 * 4 * 5이며, 결과는 60입니다.

문제는 다음과 같습니다:

입력:

n : 정수 배열의 크기 (1 ≤ n ≤ 10⁵)

정수 배열 arr : 크기 n의 배열 (1 ≤ arr[i] ≤ 1000)

m : 구간 요청의 개수 (1 ≤ m ≤ 10⁵)

구간 요청 [l, r] (1 ≤ l ≤ r ≤ n)

출력: 각 원소의 구간에 대한 곱을 구하여 출력하라.

문제 접근 방법

문제를 해결하기 위해 우선 숫자 배열의 구간 곱을 효율적으로 구하는 방법을 고려해야 합니다.
단순히 구간 [l, r]에 대해 곱을 구하려고 하면, 최악의 경우 시간복잡도가 O(n * m)이 되어 성능이 떨어질 수 있습니다.
따라서, 선형 시간 이내에 결과를 도출할 수 있는 방법을 찾아야 합니다.

1. 누적곱 배열

구간 곱을 효율적으로 구하기 위해, 누적곱(Cumulative Product) 배열을 사용할 수 있습니다.
array의 i번째 원소까지의 곱을 저장하여, 구간 곱은 다음과 같이 계산할 수 있습니다.

cumulativeProduct[i] = arr[0] * arr[1] * ... * arr[i]

이 경우, 구간 곱은 다음과 같이 구할 수 있습니다:

product(l, r) = cumulativeProduct[r] / cumulativeProduct[l-1]

여기서 cumulativeProduct[0]은 1로 초기화됩니다. 이를 통해 우리는 선형 시간 O(n)으로 누적곱 배열을 생성한 후,
각 쿼리에 대해 O(1)로 구간 곱을 계산할 수 있습니다.

2. 음수 처리

다만, 부호가 음수일 경우 음수와 양수의 곱에 따라 결과가 달라질 수 있습니다.
이러한 경우에는 음수의 개수를 파악하여 결과를 조정해야 합니다.

구간 내에 포함된 음수의 개수가 홀수이면 결과가 음수로, 짝수이면 양수로 할 수 있습니다.
이 경우, 추가적으로 음수를 선택하여 최대 곱을 구하는 로직이 필요해질 수 있습니다.

구현 코드

위의 접근 방법을 고려하여 코틀린으로 코드를 구현해보도록 하겠습니다.

fun getCumulativeProducts(arr: IntArray): IntArray {
        val n = arr.size
        val cumulativeProduct = IntArray(n)
        cumulativeProduct[0] = arr[0]
        
        for (i in 1 until n) {
            cumulativeProduct[i] = cumulativeProduct[i - 1] * arr[i]
        }
        
        return cumulativeProduct
}

이어서 구간 곱을 반환하는 함수를 작성하겠습니다.

fun rangeProduct(cumulativeProduct: IntArray, l: Int, r: Int): Int {
        if (l == 0) return cumulativeProduct[r]
        return cumulativeProduct[r] / cumulativeProduct[l - 1]
}

마지막으로, 전체 알고리즘을 결합해보겠습니다.

fun main() {
    val arr = intArrayOf(2, 3, 4, 5)
    val cumulativeProduct = getCumulativeProducts(arr)
    val queries = listOf(Pair(1, 3), Pair(0, 2))

    for (query in queries) {
        val (l, r) = query
        val result = rangeProduct(cumulativeProduct, l, r)
        println("구간 ($l, $r)의 곱: $result")
    }
}

복잡도 분석

– 시간 복잡도: O(n + m) (여기서 n은 배열의 크기, m은 요청의 수)

– 공간 복잡도: O(n) (누적곱 배열을 저장하기 위한 공간)

이러한 방법을 통해 문제를 효율적으로 해결할 수 있습니다.
누적곱 배열을 이용하면 곱을 한 번에 계산할 수 있어 각 쿼리에 대해 빠르게 결과를 도출할 수 있습니다.

결론

이번 강좌에서는 구간 곱 구하기 문제를 해결하기 위해 누적곱 배열을 사용하여 효율적인 알고리즘을 구현하였습니다.
이러한 접근법은 다양한 배열 문제를 다루는 데 유용하게 사용할 수 있습니다.

추가적인 질문이나 궁금한 점이 있으시면 댓글을 통해 문의해주시기 바랍니다. 감사합니다!