[Kotlin] 백준 23294 : 웹 브라우저 1

문제 링크

23294번: 웹 브라우저 1

---

문제 해설

[Kotlin] 백준 23300 : 웹 브라우저 2와 유사한 문제지만 캐시 용량의 제한이 추가되어 있는 문제이다. 캐시 용량을 다루는 것을 제외하면 기본적인 풀이는 동일하다.

 

각 페이지의 캐시 공간은 배열에 저장하여 사용했다.

 

뒤로 가기 공간과 앞으로 가기 공간을 각각 덱으로 구현하고 B 또는 F를 수행할 때마다 저장된 페이지와 현재 페이지를 옮기면 된다. 이 두 경우에는 이미 캐시 공간에 저장된 페이지를 이동만 하기 때문에 캐시 용량을 고려할 필요가 없다.

 

A를 수행할 때는 앞으로 가기 공간을 모두 비워야 하는데 이 과정에서 앞으로 가기 공간에 있던 페이지들이 차지하는 캐시 용량을 캐시 공간에서 제거해준다. 이후 캐시 공간에 새로 접속한 페이지의 캐시 용량을 추가하고 이 값이 \(c\)를 초과하였다면 뒤로 가기 공간의 가장 앞에서부터 캐시 용량의 총합이 \(c\) 이하가 될때까지 페이지와 캐시 용량을 제거한다.

 

C를 수행할 때는 압축되어 삭제되는 페이지의 캐시 용량만큼 캐시 용량의 총합에서 제거해주면 된다.

Code

import java.util.StringTokenizer

fun main() = with(System.`in`.bufferedReader()) {
    val bw = System.out.bufferedWriter()
    val (n, q, c) = readLine().split(' ').map { it.toInt() }
    val cache = IntArray(1) + StringTokenizer(readLine()).run { IntArray(n) { nextToken().toInt() } }
    val back = ArrayDeque<Int>()
    val front = ArrayDeque<Int>()
    var cacheSize = 0
    var current = 0
    for (i in 1..q) {
        val st = StringTokenizer(readLine())
        when (st.nextToken()) {
            "B" -> {
                if (back.isNotEmpty()) {
                    front.addFirst(current)
                    current = back.removeLast()
                }
            }
            "F" -> {
                if (front.isNotEmpty()) {
                    back.addLast(current)
                    current = front.removeFirst()
                }
            }
            "A" -> {
                while (front.isNotEmpty()) cacheSize -= cache[front.removeFirst()]
                if (current != 0) back.addLast(current)
                current = st.nextToken().toInt()
                cacheSize += cache[current]
                while (cacheSize > c) cacheSize -= cache[back.removeFirst()]
            }
            "C" -> {
                var j = 1
                while (j < back.size) {
                    if (back[j - 1] == back[j]) cacheSize -= cache[back.removeAt(j--)]
                    j++
                }
            }
        }
    }
    bw.write("$current\n")
    bw.write("${back.takeIf { it.isNotEmpty() }?.reversed()?.joinToString(" ") ?: -1}\n")
    bw.write("${front.takeIf { it.isNotEmpty() }?.joinToString(" ") ?: -1}")
    bw.close()
}