백준 11000번
https://www.acmicpc.net/problem/11000
PriorityQueue를 사용하는 자료구조 문제이다.
val comp = object : Comparator<Lecture> {
override fun compare(o1: Lecture?, o2: Lecture?): Int {
if (o1!!.startTime == o2!!.startTime) {
return o1.endTime - o2.endTime
}
return o1.startTime - o2.startTime
}
}
val pQue = PriorityQueue(comp)
평소에 PriorityQueue를 쓸 때 객체를 사용하게 되면 Comparable을 구현해야 했었는데, 이걸 객체 만들 때 구현했었다.
근데 다른 분들의 코드를 보다가 위와 같은 방식으로 Comparator를 람다 형식으로 따로 빼놓고 나중에 PriorityQueue에 붙여주기만 해도 정렬 조건을 구현해 줄 수 있다는 걸 알게 됐다. 시간을 비교해 보면 이게 조금 더 비효율적인가 싶긴 해도 새로운 방법을 알게 되어서 뿌듯했다
val compLambda = Comparator<Lecture>() { o1, o2 ->
if (o1.startTime == o2.startTime) {
o1.endTime - o2.endTime
}
o1.startTime - o2.startTime
}
val pQue = PriorityQueue(compLambda)
import java.io.*
import java.util.*
// Input
private lateinit var br: BufferedReader
// Variables
private var N = 0
private var pQue: PriorityQueue<Lecture> = PriorityQueue()
private var timePque = PriorityQueue<Int>()
private lateinit var lectures: Array<Lecture>
private data class Lecture(
var startTime: Int, // 수업 시작 시간
var endTime: Int // 수업 끝나는 시간
) : Comparable<Lecture> {
// End of Class
override fun compareTo(other: Lecture): Int {
if (startTime == other.startTime) {
return endTime - other.endTime
}
return startTime - other.startTime
}
} // End of Lecture class
fun main() {
br = BufferedReader(InputStreamReader(System.`in`))
val bw = BufferedWriter(OutputStreamWriter(System.`out`))
val sb = StringBuilder()
input()
var index = 0
while (pQue.isNotEmpty()) {
lectures[index++] = pQue.poll()
}
timePque.offer(lectures[0].endTime)
for (i in 1 until N) {
if (timePque.peek() <= lectures[i].startTime) {
timePque.poll()
}
timePque.offer(lectures[i].endTime)
}
sb.append(timePque.size)
bw.write(sb.toString())
bw.close()
} // End of main
private fun input() {
N = br.readLine().toInt()
lectures = Array(N) { Lecture(0, 0) }
for (i in 0 until N) {
val st = StringTokenizer(br.readLine())
pQue.offer(
Lecture(
st.nextToken().toInt(), st.nextToken().toInt()
)
)
}
} // End of input