[백준 2357] 최솟값과 최댓값 (Kotlin)

🏆 문제 난이도
- Gold I

🔗 문제 링크
https://www.acmicpc.net/problem/2357

📝 문제 분석 & 접근

수열의 크기를 N, 질의의 수를 M이라고 할 때, 각 질의마다 O(N)의 시간이 걸리므로, 매번 순회하면서 최솟값과 최댓값을 찾으면 전체 시간 복잡도는 O(NM)이 될껍니다.

즉, 최악의 경우 수열의 크기 최대 100,000 그리고 질의의 수 최대 100,000이므로 연산 횟수가 10^10이 될 수 있습니다.

이처럼 많은 질의를 빠르게 처리해야 할 때는, 질의에 답하기 위해 미리 데이터를 가공해두는 효율적인 자료구조가 필요합니다.

이 문제에 가장 적합한 자료구조는 바로 세그먼트 트리(Segment Tree)입니다

 

세그먼트 트리가 무엇인지는 따로 설명하지 않겠습니다만, 괜찮은 설명글을 하나 달아두겠습니다.

👉 세그먼트 트리 설명 링크

---

✨ 핵심 아이디어

- 세그먼트 트리

세그먼트 트리는 특정 구간에 대한 질의를 빠르게 처리하기 위해 고안된 자료구조입니다.

이 문제의 핵심은 최솟값과 최댓값을 동시에 구해야 한다는 점이죠.

이를 위해 두 개의 세그먼트 트리를 각각 구축하는 전략을 사용할 수 있습니다.

 

 

• 최소 세그먼트 트리: 각 노드가 담당하는 구간의 최솟값을 저장하는 트리입니다.
• 최대 세그먼트 트리: 각 노드가 담당하는 구간의 최댓값을 저장하는 트리입니다.

 

 

코드에서 사용한 개념들을 짚으며 설명드리겠습니다.

1. 세그먼트 트리 구축 (build)

buildSegmentTree 함수는 재귀적으로 트리를 만들어 나갑니다.

• 리프 노드: 배열의 실제 원소 값을 저장합니다.
• 부모 노드: 자식 노드들의 값을 기반으로 자신의 값을 결정합니다.
  • 최소 트리의 경우: min(left_child, right_child)
  • 최대 트리의 경우: max(left_child, right_child)

이렇게 트리를 구축하면, 루트 노드에는 전체 구간의 최솟값과 최댓값이 각각 저장되게 됩니다.

이 과정은 O(N)의 시간이 소요됩니다.

2. 구간 탐색 (search)

searchMaxMin 함수를 이용해 질의 구간 [a, b]에 대한 최솟값과 최댓값을 탐색합니다.

• 완전 포함: 노드의 구간이 질의 구간에 완전히 포함될 경우, 더 이상 재귀를 진행하지 않고 해당 노드의 값을 결과에 반영합니다.
• 부분 포함 (겹침): 노드의 구간이 질의 구간과 겹치기만 할 경우, 양쪽 자식 노드로 재귀를 호출하여 더 자세히 탐색합니다.
• 포함되지 않음: 노드의 구간이 질의 구간과 전혀 겹치지 않으면 탐색을 중단합니다.

이러한 방식으로 탐색을 진행하면, 불필요한 노드를 탐색하지 않고 빠르게 결과를 얻을 수 있습니다.

이 과정은 O(log N)의 시간이 소요됩니다.

---

💻 코드

import java.io.StreamTokenizer
import kotlin.math.max
import kotlin.math.min

var n = 0
var min = 1000000001
var max = -1
lateinit var elements: IntArray
lateinit var minTree: IntArray
lateinit var maxTree: IntArray

fun main() = with(StreamTokenizer(System.`in`.bufferedReader())) {
    val sb = StringBuilder()

    fun StreamTokenizer.nextInt(): Int {
        nextToken()
        return nval.toInt()
    }

    n = nextInt()
    val m = nextInt()
    elements = IntArray(n+1){ it -> if(it == 0) 0 else nextInt() }

    // segment tree 사이즈
    val treeSize = Math.pow(2.0, Math.ceil(Math.log(n.toDouble()) / Math.log(2.0)) + 1).toInt()

    minTree = IntArray(treeSize)
    maxTree = IntArray(treeSize)
    buildSegmentTree(true, minTree, 1, n, 1)
    buildSegmentTree(false, maxTree, 1, n, 1)

    repeat(m) {
        val a = nextInt()
        val b = nextInt()
        min = 1000000001
        max = -1
        searchMaxMin(true, minTree, 1, n, 1, a, b)
        searchMaxMin(false, maxTree, 1, n, 1, a, b)
        sb.append(min).append(" ").append(max).append("\n")
    }
    println(sb)
}

// type이 true이면 최소트리
fun buildSegmentTree(type: Boolean, tree: IntArray, start: Int, end: Int, node: Int) {
    if (start == end) tree[node] = elements[start]
    else {
        val mid = (start + end) / 2
        buildSegmentTree(type, tree, start, mid, node * 2)
        buildSegmentTree(type, tree, mid + 1, end, node * 2 + 1)

        if (type) {
            tree[node] = if(tree[node * 2] < tree[node * 2 + 1]) tree[node * 2] else tree[node * 2 + 1]
        } else {
            tree[node] = if(tree[node * 2] > tree[node * 2 + 1]) tree[node * 2] else tree[node * 2 + 1]
        }
    }
}

// type true이면 최소
fun searchMaxMin(type: Boolean, tree: IntArray, start: Int, end: Int, node: Int, left: Int, right: Int) {
    if(left > end || right < start) return
    if (left <= start && end <= right) {
        if(type) min = min(min, tree[node])
        else max = max(max, tree[node])
        return
    }

    val mid = (start + end) / 2
    searchMaxMin(type, tree, start, mid, node * 2, left, right)
    searchMaxMin(type, tree, mid + 1, end, node * 2 + 1, left, right)
}