[백준 7578] 공장 (Kotlin)

🏆 문제 난이도
- Platinum V

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

📝 문제 분석 & 접근

아이디어는 간단합니다.

1. A를 순서대로 순회하며, 같은 값을 가진 B의 index가 어딘지를 찾습니다.
2. 찾은 B index보다 뒤에 값들 중에 방문한 적이 있는지를 확인하고 전부 더합니다. (SegmentTree에서 Query 역할)
   방문한 적 없다면 겹치는 선이 없는 것입니다.
3. SegmentTree Update를 통해서 방문한 노드와 해당 노드를 포함하는 노드들에 1을 더해줍니다.
   (새로운 노드에 방문했다는 의미로 1을 더해주는 것입니다.)
4. 2.에서 찾은 Sum 값들을 전부 더하고 출력합니다.

---

💻 코드

import java.io.StreamTokenizer

lateinit var tree: LongArray

fun main() = with(StreamTokenizer(System.`in`.bufferedReader())) {
    fun StreamTokenizer.nextInt(): Int{
        nextToken()
        return nval.toInt()
    }

    val n = nextInt()
    val arrA = IntArray(n+1) { if (it == 0) 0 else nextInt() }
    val mapB = HashMap<Int, Int>()
    (1..n).forEach{ mapB[nextInt()] = it }

    tree = LongArray(n * 4)
    var ans = 0L

    for (i in 1..n) {
        val valA = arrA[i]
        val valB = mapB[valA]
        ans += sum(1, n, 1, valB!! + 1, n)
        update(1, n, 1, valB, 1)
    }
    println(ans)
}

fun sum(start: Int, end: Int, node: Int, left: Int, right: Int): Long {
    if(end < left || right < start) return 0L
    if(left <= start && end <= right) return tree[node]

    val mid = (start + end) / 2
    return sum(start, mid, node * 2, left, right) + sum(mid + 1, end, node * 2 + 1, left, right)
}

fun update(start: Int, end: Int, node: Int, idx: Int, diff: Int) {
    if(idx < start || end < idx) return

    tree[node] = tree[node] + diff

    if (start != end) {
        val mid = (start + end) / 2
        update(start, mid, node * 2, idx, diff)
        update(mid + 1, end, node * 2 + 1, idx, diff)
    }
}