[BOJ] 7493 Collisions - P5

TaeGN·2024년 9월 30일

algorithm kotlin

BOJ Platinum Challenge

목록 보기

108/114

문제풀이

공을 x에 대하여 오름차순 정렬했을 때, 세그먼트 트리에서 내 속도보다 큰 공의 개수를 구하면 된다.
- 충돌 후 속도가 변하는 것은 공이 서로를 통과하는 것과 같은 효과이다.

주의사항

입력 데이터에 오류가 있다. split(" ")으로 구분하면 NumberFormat 오류가 발생하는 것으로 보아 띄어쓰기가 2개 이상인 경우가 있는 것 같다.

소요시간

40분

package 백준.Platinum.P5.p7493_Collisions

import java.util.StringTokenizer
import kotlin.math.ceil
import kotlin.math.log2

class SegTree(val N: Int) {
    private val tree = IntArray(1 shl (ceil(log2(N.toDouble())).toInt() + 1))
    fun update(idx: Int, diff: Int, start: Int = 0, end: Int = N - 1, treeIdx: Int = 1) {
        if (end < idx || idx < start) return
        tree[treeIdx] += diff
        if (start == end) return
        val mid = (start + end) / 2
        update(idx, diff, start, mid, treeIdx * 2)
        update(idx, diff, mid + 1, end, treeIdx * 2 + 1)
    }

    fun query(left: Int, right: Int, start: Int = 0, end: Int = N - 1, treeIdx: Int = 1): Int {
        if (end < left || right < start) return 0
        if (left <= start && end <= right) return tree[treeIdx]
        val mid = (start + end) / 2
        return query(left, right, start, mid, treeIdx * 2) + query(left, right, mid + 1, end, treeIdx * 2 + 1)
    }
}

data class Ball(val x: Long, val v: Int)

fun main() {
    val N = readln().trim().toInt()
    val ballList = List(N) {
        val st = StringTokenizer(readln())
        Ball(st.nextToken().toLong(), st.nextToken().toInt())
    }.sortedBy { it.x }
    val speedToIdxMap = mutableMapOf<Int, Int>()
    ballList.asSequence().map { it.v }.distinct().sorted().forEachIndexed { index, i -> speedToIdxMap[i] = index }
    val size = speedToIdxMap.size
    val segTree = SegTree(size)
    var result = 0L
    for ((_, v) in ballList) {
        val idx = speedToIdxMap[v]!!
        if (idx < size - 1) result += segTree.query(idx + 1, size - 1)
        segTree.update(idx, 1)
    }
    println(result)
}