[BOJ] 13445 부분 수열 XOR - P2

문제풀이

1. trie 자료 구조를 만들고 0을 넣는다.
2. 현재까지의 xor누적 값을 trie 내부의 숫자와 비교하여 K보다 작은 숫자의 개수를 구한다.
3. 현재까지의 xor누적 값을 trie에 넣는다.
4. N개의 배열을 순회하며 2, 3번을 반복한다.

---

주의사항

---

소요시간

20분

---

package 백준.Platinum.P2.p13445_부분수열XOR

class Trie(val idx: Int) {
    val children = Array<Trie?>(2) { null }
    var count = 0
    fun add(num: Int) {
        count++
        if (idx == 17) return
        getChild(getBit(num)).add(num)
    }

    private fun getChild(bit: Int): Trie {
        if (children[bit] == null) children[bit] = Trie(idx + 1)
        return children[bit]!!
    }

    private fun getBit(num: Int) = if ((num and (1 shl (16 - idx))) != 0) 1 else 0

    fun countLowerK(num: Int, k: Int, sum: Int = 0): Int {
        if (sum >= k) return 0
        if (sum + (1 shl (17 - idx)) <= k) return count
        var result = 0
        val bit = getBit(num)
        if (children[bit] != null) {
            result += children[bit]!!.countLowerK(num, k, sum)
        }
        if (children[(bit + 1) % 2] != null) {
            result += children[(bit + 1) % 2]!!.countLowerK(num, k, sum + (1 shl (16 - idx)))
        }
        return result
    }
}

fun main() {
    val (N, K) = readln().trim().split(" ").map(String::toInt)
    val aArr = readln().trim().split(" ").map(String::toInt)
    val trie = Trie(0)
    var result = 0L
    var subsetXor = 0
    trie.add(0)
    for (a in aArr) {
        subsetXor = subsetXor xor a
        result += trie.countLowerK(subsetXor, K)
        trie.add(subsetXor)
    }
    println(result)
}

https://github.com/TaeGN/Algorithm/blob/master/src/%EB%B0%B1%EC%A4%80/Platinum/P2/p13445_%EB%B6%80%EB%B6%84%EC%88%98%EC%97%B4XOR/p13445_%EB%B6%80%EB%B6%84%EC%88%98%EC%97%B4XOR.kt

---

문제링크

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

---

회고

K보다 작은 값의 개수를 구하는 부분을 구현하는 것이 재밌었다.