[Kotlin] 백준 21773 : 가희와 프로세스 1

문제 링크

21773번: 가희와 프로세스 1

---

---

문제 해설

우선순위 큐와 Comparable 인터페이스를 구현한 클래스를 사용하여 답을 찾아야 한다. 문제를 해결하는 과정은 다음과 같다.

1. 각 프로세스의 우선순위가 같다면 id가 낮은 순으로, 다르다면 우선순위를 높은 순으로 정렬하도록 Comparable 인터페이스를 구현한 클래스를 선언한다.
2. 우선순위 큐에 입력을 토대로 생성한 프로세스 객체를 모두 삽입한다.
3. 우선순위 큐의 Root 요소를 꺼내어 다음 연산을 수행한다.
   • null이라면(= 스케줄러가 비어있다면) 반복문을 종료한다.
   • 꺼낸 프로세스의 남은 시간과 우선순위를 1씩 감소시킨다.
   • 꺼낸 프로세스의 남은 시간이 0이 아니라면 스케줄러에 다시 삽입한다.

여기서 꺼낸 프로세스를 제외한 나머지 프로세스의 우선순위를 1 증가시키는 대신 꺼낸 프로세스의 우선순위를 1 감소시키는 방법을 택하였는데, 우선순위라는 것은 상대적이기 때문이다. 프로세스의 최대 개수가 100,000개이고 실행시간의 최대치가 1,000,000이므로, 매번 나머지 프로세스의 우선순위를 증가시켰다가는 굉장히 많은 시간이 소요된다. 따라서, 꺼낸 프로세스의 우선순위를 감소시키는 것이 더 효율적이다.

 

프로세스 클래스에 Comparable 인터페이스를 구현하지 않고 우선순위 큐에 Comparator 객체를 적용해도 문제를 해결할 수 있으나, Comparable을 사용하는 것이 시간 복잡도와 공간 복잡도 상으로 더 효율적이다.

---

Code

 

Comparable

import java.util.PriorityQueue
import java.util.StringTokenizer

fun main() = with(System.`in`.bufferedReader()) {
    val bw = System.out.bufferedWriter()
    val (t, n) = readLine().split(' ').map { it.toInt() }
    val scheduler = PriorityQueue<Process>()
    repeat(n) {
        StringTokenizer(readLine()).apply {
            scheduler.add(Process(nextToken().toInt(), nextToken().toInt(), nextToken().toInt()))
        }
    }
    for (i in 1..t) {
        val process = scheduler.poll()?.apply {
            bw.write("$id\n")
            time--
            priority--
        } ?: break

        if (process.time > 0)
            scheduler.add(process)
    }
    bw.close()
}

class Process(val id: Int, var time: Int, var priority: Int) : Comparable<Process> {
    override fun compareTo(other: Process) = if (other.priority == this.priority) this.id - other.id else other.priority - this.priority
}

 

Comparator

import java.util.PriorityQueue
import java.util.StringTokenizer

fun main() = with(System.`in`.bufferedReader()) {
    val bw = System.out.bufferedWriter()
    val (t, n) = readLine().split(' ').map { it.toInt() }
    val scheduler = PriorityQueue<Process> {
        o1, o2 -> if (o2.priority == o1.priority) o1.id - o2.id else o2.priority - o1.priority 
    }
    repeat(n) {
        StringTokenizer(readLine()).apply { 
            scheduler.add(Process(nextToken().toInt(), nextToken().toInt(), nextToken().toInt())) 
        }
    }
    for (i in 1..t) {
        if (scheduler.isEmpty()) break
        val process = scheduler.poll().apply {
            bw.write("$id\n")
            time--
            priority--
        }

        if (process.time > 0)
            scheduler.add(process)
    }
    bw.close()
}

class Process(val id: Int, var time: Int, var priority: Int)

---

위가 Comparable을 사용한 것이고, 아래가 Comparator를 사용한 결과이다. 메모리는 약 3배에 가까운 차이가 나고, 시간은 약 35%만큼 차이가 날 정도로 Comparable 쪽이 효율적이라는 것을 알 수 있다.