[BOJ] 13505 두 수 XOR - P3

문제풀이

1. trie 자료 구조를 사용하여 각 숫자를 2진수로 표현한 문자를 저장한다.
2. N개의 2진수를 순회하며 각각의 xor값이 가장 커질 수 있는 경우를 구한다. (trie 자료 구조를 탐색하며 자기 자신의 비트와 다른 값을 우선해서 탐색해 나간다.)
3. 2번에서 구한 것 중에 가장 큰 값을 선택한다.

---

주의사항

---

소요시간

35분

---

package 백준.Platinum.P3.p13505_두수XOR

class Trie(val idx: Int = 0) {
    private val children = Array<Trie?>(2) { null }
    fun add(str: String) {
        if (idx == str.length) return
        if (children[str[idx].digitToInt()] == null) children[str[idx].digitToInt()] = Trie(idx + 1)
        children[str[idx].digitToInt()]!!.add(str)
    }

    fun find(str: String): String {
        if (str.length == idx) return ""
        return if (children[(str[idx].digitToInt() + 1) % 2] != null) {
            "${(str[idx].digitToInt() + 1) % 2}${children[(str[idx].digitToInt() + 1) % 2]!!.find(str)}"
        } else "${str[idx].digitToInt()}${children[str[idx].digitToInt()]!!.find(str)}"
    }
}

fun main() {
    val N = readln().toInt()
    val aArr = readln().trim().split(" ").map(String::toInt)
        .map { num -> num.toString(2).let { "0".repeat(30 - it.length) + it } }
    val trie = Trie()
    aArr.forEach { trie.add(it) }
    println(aArr.maxOf { it.toInt(2) xor trie.find(it).toInt(2) })
}

https://github.com/TaeGN/Algorithm/blob/master/src/%EB%B0%B1%EC%A4%80/Platinum/P3/p13505_%EB%91%90%EC%88%98XOR/p13505_%EB%91%90%EC%88%98XOR.kt

---

문제링크

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