[BOJ] 14413 Poklon - P1

문제풀이

1. 값의 범위가 값의 개수보다 매우 크므로 hashMap을 활용하여 좌표를 치환한다.
2. 쿼리를 정렬한다.
3. mo's 알고리즘을 활용하여 구간에 2번 등장하는 숫자의 개수를 구한다.

---

주의사항

---

소요시간

15분

---

package 백준.Platinum.P1.p14413_Poklon

import kotlin.math.sqrt

fun main() {
    val (N, Q) = readln().trim().split(" ").map(String::toInt)
    val nArr = readln().trim().split(" ").map(String::toInt).toIntArray()
    val qArr = Array(Q) { idx -> readln().trim().split(" ").map { it.toInt() - 1 }.let { Triple(idx, it[0], it[1]) } }
    val sqrtN = sqrt(N.toDouble()).toInt()
    qArr.sortWith(compareBy({ it.second / sqrtN }, { it.third }))
    var nIdx = 0
    val nToIdxMap = mutableMapOf<Int, Int>()
    for ((i, n) in nArr.withIndex()) {
        if (n !in nToIdxMap) nToIdxMap[n] = nIdx++
        nArr[i] = nToIdxMap[n]!!
    }
    val countArr = IntArray(N)
    val resultArr = IntArray(Q)
    var result = 0
    var pl = 0
    var pr = -1
    for ((idx, l, r) in qArr) {
        if (pl > l) {
            for (i in l until pl) {
                if (countArr[nArr[i]] == 2) result--
                if (++countArr[nArr[i]] == 2) result++
            }
        }
        if (pr < r) {
            for (i in (pr + 1)..r) {
                if (countArr[nArr[i]] == 2) result--
                if (++countArr[nArr[i]] == 2) result++
            }
        }
        if (pl < l) {
            for (i in pl until l) {
                if (countArr[nArr[i]] == 2) result--
                if (--countArr[nArr[i]] == 2) result++
            }
        }
        if (pr > r) {
            for (i in (r + 1)..pr) {
                if (countArr[nArr[i]] == 2) result--
                if (--countArr[nArr[i]] == 2) result++
            }
        }
        pl = l
        pr = r
        resultArr[idx] = result
    }
    println(resultArr.joinToString("\n"))
}

https://github.com/TaeGN/Algorithm/blob/master/src/%EB%B0%B1%EC%A4%80/Platinum/P1/p14413_Poklon/p14413_Poklon.kt

---

문제링크

https://www.acmicpc.net/problem/14413