문제 설명
주어진 숫자 배열의 구간에 해당하는 곱을 구하는 문제입니다.
예를 들어, 숫자 배열 [2, 3, 4, 5]가 주어졌을 때,
구간 [1, 3]에 해당하는 곱은 3 * 4 * 5이며, 결과는 60입니다.
문제는 다음과 같습니다:
입력:
n: 정수 배열의 크기 (1 ≤n≤ 105)- 정수 배열
arr: 크기n의 배열 (1 ≤arr[i]≤ 1000)m: 구간 요청의 개수 (1 ≤m≤ 105)- 구간 요청
[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) (누적곱 배열을 저장하기 위한 공간)
이러한 방법을 통해 문제를 효율적으로 해결할 수 있습니다.
누적곱 배열을 이용하면 곱을 한 번에 계산할 수 있어 각 쿼리에 대해 빠르게 결과를 도출할 수 있습니다.
결론
이번 강좌에서는 구간 곱 구하기 문제를 해결하기 위해 누적곱 배열을 사용하여 효율적인 알고리즘을 구현하였습니다.
이러한 접근법은 다양한 배열 문제를 다루는 데 유용하게 사용할 수 있습니다.
추가적인 질문이나 궁금한 점이 있으시면 댓글을 통해 문의해주시기 바랍니다. 감사합니다!