[AtCoder] AtCoder Beginner Contest 330 E. Mex and Update

문제풀이

1. 0 ~ N까지의 숫자의 개수를 카운팅한다.
2. 숫자의 개수가 0인 것을 treeSet에 저장하며 mex값을 구한다.

---

주의사항

---

소요시간

15분

---

package AtCoder.ProblemList.Difficulty800_1199.MexandUpdate

import java.util.TreeSet

fun main() {
    val (N, Q) = readln().trim().split(" ").map(String::toInt)
    val mex = TreeSet<Int>()
    val countArr = IntArray(N + 1)
    val A = readln().trim().split(" ").map(String::toInt).toIntArray()
    A.forEach { if (it <= N) countArr[it]++ }
    countArr.forEachIndexed { index, i -> if (i == 0) mex.add(index) }
    val sb = StringBuilder()
    repeat(Q) {
        val (i, x) = readln().trim().split(" ").map(String::toInt)
        if (A[i - 1] != x) {
            if (A[i - 1] <= N && --countArr[A[i - 1]] == 0) mex.add(A[i - 1])
            if (x <= N && ++countArr[x] == 1) mex.remove(x)
            A[i - 1] = x
        }
        sb.appendLine(mex.first())
    }
    println(sb)
}

---

문제링크

https://atcoder.jp/contests/abc330/tasks/abc330_e