[Kotlin] 백준 1700 : 멀티탭 스케줄링

문제 링크

1700번: 멀티탭 스케줄링

---

문제 해설

OS의 페이징 기법을 모티브로 한 문제인 것 같다. 멀티탭 구멍의 개수는 메모리의 크기를, 각 전기용품은 메모리에 적재되는 페이지라고 볼 수 있다. 페이징 기법을 위한 페이지 교체 알고리즘은 FIFO, LRU, LFU 등 다양한 종류가 있는데, 이 문제에서 사용할 알고리즘은 OPT(Optimal) 알고리즘이다.

 

OPT 알고리즘은 아래와 같이 동작한다.

• 이미 메모리에 페이지가 적재되어 있으면 다음 페이지로 넘어간다.
• 메모리에 페이지가 적재되어 있지 않고 메모리에 빈 공간이 있을 경우 페이지를 적재한다.
• 메모리에 페이지가 적재되어 있지 않고 메모리에 빈 공간도 없을 경우 적재된 페이지 중 이후에 사용되지 않을 페이지를 제거하고 새로운 페이지를 적재한다.
  • 적재된 페이지가 모두 이후에 사용될 페이지라면 그 중 가장 오랫동안 사용되지 않을 페이지(가장 나중에 사용될 페이지)를 제거하고 새로운 페이지를 적재한다.

여기서 메모리 = 멀티탭, 페이지 = 전기용품으로 치환해서 구현하면 된다.

 

각각의 전기용품은 독립적이기 때문에(같은 번호의 전기용품은 모두 같은 전기용품이기 때문에) 멀티탭은 Set을 사용하여 구현할 수 있다. Set의 크기가 N보다 작은 경우에는 아직 멀티탭에 빈 구멍이 존재하는 경우이므로 전기용품을 추가하고 다음으로 넘어가면 된다. 요소의 중복을 허용하지 않는 Set이기 때문에 중복되는 요소를 따로 걸러줄 필요는 없다.

 

Set의 크기 = N이 되었다면 사용할 전기용품이 멀티탭에 꽂혀있지 않은 경우에만 연산을 수행하면 된다. 멀티탭에 꽂힌 전기용품 중 다음에 사용할 전기용품 목록에 포함되지 않는 것이 있다면 해당 전기용품을 제거하고 새로운 전기용품을 추가한다. 멀티탭에 꽂힌 모든 전기용품이 다음에 사용할 전기용품 목록에 포함된다면 그 중 가장 나중에 사용될 전기용품을 제거하고 새로운 전기용품을 추가한다.

Code

import java.util.StringTokenizer

fun main() = with(System.`in`.bufferedReader()) {
    val (n, k) = readLine().split(' ').map { it.toInt() }
    val order = StringTokenizer(readLine()).run { IntArray(k) { nextToken().toInt() } }
    val plug = HashSet<Int>()
    var result = 0
    loop@ for (i in order.indices) {
        if (plug.size < n) {
            plug.add(order[i])
            continue
        }
        if (order[i] !in plug) {
            var latestItem = 0
            val nextOrder = order.sliceArray(i + 1..order.lastIndex)
            for (item in plug) {
                if (item !in nextOrder) {
                    plug.remove(item)
                    plug.add(order[i])
                    result++
                    continue@loop
                }
                latestItem = maxOf(latestItem, nextOrder.indexOf(item))
            }
            plug.remove(nextOrder[latestItem])
            plug.add(order[i])
            result++
        }
    }
    println(result)
}