[Kotlin] 백준 21939 : 문제 추천 시스템 Version 1

문제 링크

21939번: 문제 추천 시스템 Version 1

---

---

문제 해설

정렬과 탐색을 동시에 빠르게 하기 위해서 TreeSet을 사용하여 풀었다. 문제의 번호를 인덱스로 하여 문제의 난이도를 배열로 따로 관리했고, 문제 번호는 TreeSet에서 난이도가 높은 순으로, 난이도가 같다면 문제 번호가 큰 순서대로 정렬되도록 Comporator를 구현했다. 그 후 주어지는 문제의 정보를 저장한 후 명령어별로 분기를 수행하면 된다.

 

• recommend : \(x\)가 \(1\)이면 TreeSet의 첫번째 값을, \(-1\)이면 TreeSet의 마지막 값을 출력한다. TreeSet의 Comparator를 오름차순으로 구현했다면 반대로 출력한다.
• add : 처음 문제 정보를 추가할 때와 동일하게 문제 정보를 추가한다.
• solved : \(P\)번 문제를 TreeSet에서 제거하고 P번의 난이도를 0으로 리셋한다.

---

Code

import java.util.StringTokenizer
import java.util.TreeSet

fun main() = with(System.`in`.bufferedReader()) {
    val bw = System.out.bufferedWriter()
    val difficulty = IntArray(100001)
    val problems = TreeSet<Int> { o1, o2 -> if (difficulty[o1] == difficulty[o2]) o2 - o1 else difficulty[o2] - difficulty[o1] }
    repeat(readLine().toInt()) {
        StringTokenizer(readLine()).apply {
            problems.add(nextToken().toInt().also { n -> difficulty[n] = nextToken().toInt() })
        }
    }
    repeat(readLine().toInt()) {
        val st = StringTokenizer(readLine())
        when (st.nextToken()) {
            "recommend" -> bw.write(if (st.nextToken() == "1") "${problems.first()}\n" else "${problems.last()}\n")
            "add" -> problems.add(st.nextToken().toInt().also { n -> difficulty[n] = st.nextToken().toInt() })
            "solved" -> {
                val n = st.nextToken().toInt()
                problems.remove(n)
                difficulty[n] = 0
            }
        }
    }
    bw.close()
}