백준 11000 강의실 배정 Kotlin

: ) YOUNG·2023년 7월 5일
1

알고리즘

목록 보기
221/411
post-thumbnail

백준 11000번
https://www.acmicpc.net/problem/11000

문제




생각하기


  • PriorityQueue를 사용하는 자료구조 문제이다.

    • 정렬 조건을 구현해야 한다.

동작

  • 일반 Comparator

    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에 붙여주기만 해도 정렬 조건을 구현해 줄 수 있다는 걸 알게 됐다. 시간을 비교해 보면 이게 조금 더 비효율적인가 싶긴 해도 새로운 방법을 알게 되어서 뿌듯했다

  • 람다 Comparator

    val compLambda = Comparator<Lecture>() { o1, o2 ->
        if (o1.startTime == o2.startTime) {
            o1.endTime - o2.endTime
        }
        o1.startTime - o2.startTime
    }

    val pQue = PriorityQueue(compLambda)
    


코드


Kotlin


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

0개의 댓글