[Kotlin] 백준 18917 : 수열과 쿼리 38

문제 링크

18917번: 수열과 쿼리 38

---

---

문제 해설

수열, 배열이라는 말이 있어서 실제로 리스트를 만들어서 구현하려고 할 수 있는데 함정이 있다. 쿼리의 개수가 최대 50만개이기 떄문에 실제 리스트에 25만개의 요소를 추가하고, 합이나 XOR 결과를 25만번 출력하게 되면 \(250,001\times250,000=62,500,250,000\)가 되어 약 625초의 시간이 걸리게 된다. 따라서, 실제 리스트를 구현하지 않고 답을 구해야 한다.

 

문제에서 요구하는 출력은 모든 원소의 합 또는 모든 원소의 XOR 결과이다. 즉, 실제 리스트를 구현하지 않고 합과 XOR만 계산하면 된다는 뜻이다. 합을 구하는 경우엔 1번 쿼리가 들어오면 x를 더하고, 2번 쿼리가 들어오면 x를 빼주면 된다. XOR의 경우엔 x XOR x = 0이기 때문에 1번 쿼리, 2번 쿼리 모두 이전 결과에 x를 XOR 해주면 된다.

 

마지막으로 x의 최대 크기가 1,000,000,000이기 때문에 3번 쿼리의 결과가 Int 범위를 초과할 수 있으므로 Long형으로 계산해야 한다는 것만 주의하면 된다.

---

Code

import java.util.StringTokenizer

fun main() = with(System.`in`.bufferedReader()) {
    val bw = System.out.bufferedWriter()
    var sum = 0L
    var XOR = 0L
    repeat(readLine().toInt()) {
        StringTokenizer(readLine()).apply {
            when (nextToken()) {
                "1" -> {
                    nextToken().toLong().also { n ->
                        sum += n
                        XOR = XOR xor n
                    }
                }
                "2" -> {
                    nextToken().toLong().also { n ->
                        sum -= n
                        XOR = XOR xor n
                    }
                }
                "3" -> bw.write("${sum}\n")
                "4" -> bw.write("${XOR}\n")
            }
        }
    }
    bw.close()
}