문제풀이
- 현재 인덱스보다 큰 인덱스, 현재 값보다 작은 값의 개수만큼 카운팅해주면 된다.
- 세그먼트 트리를 이용하여 값이 작은 순으로 넣어주고, 현재 인덱스보다 큰 인덱스의 개수를 구하면 된다.
주의사항
소요시간
10분
package 백준.Platinum.P5.p1517_버블소트
class SegTree(val N: Int) {
val tree = LongArray(N * 4)
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.toLong()
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 = 1, end: Int = N - 1, treeIdx: Int = 1): Long {
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)
}
}
fun main() {
val N = readln().toInt()
val A = readln().trim().split(" ").map(String::toInt).mapIndexed { index, i -> index to i }.sortedBy { it.second }
val segTree = SegTree(N)
var result = 0L
for ((idx, _) in A) {
result += segTree.query(idx + 1, N - 1)
segTree.update(idx, 1)
}
println(result)
}