[Kotlin] 백준 23309 : 철도 공사

문제 링크

23309번: 철도 공사

---

---

문제 해설

시간 초과 때문에 골머리를 썩힌 문제다. 분류상으로는 연결 리스트 문제인데 그렇다고 연결 리스트를 사용할 수는 없다. 연결 리스트의 경우 탐색하는데 걸리는 시간 복잡도가 \(O(n)\)인데, \(500,000 \times 1,500,000=7500\)억이 되어 너무 많은 시간이 걸리기 때문이다. 따라서 훨씬 효율적인 탐색 방법이 필요하다.

 

결국 배열을 사용하기로 했다. 역 고유 번호를 인덱스로 하여 이전역과 다음역을 저장할 배열을 프로퍼티로 갖는 클래스를 선언해서 각 공사 정보에 대한 처리를 진행했다.

 

그런데 이렇게 탐색의 시간 복잡도를 \(O(1)\)로 줄였는데도 시간 초과가 났다. 시간 제한이 2초인데 추가 시간이 없는게 가장 큰 문제같다. 결국 입출력쪽에서도 시간을 줄여보기로 했다. 원래는 BufferedWriter로 출력을 했는데, 검색을 해보다가 문자열의 + 연산의 시간이 오래 걸린다는 말을 봤다. 문자열 템플릿으로 BufferedWriter에 출력값을 쓸 때 Kotlin의 문자열 템플릿 내부에서 문자열의 + 연산이 일어나는건가 싶어서 StringBuilder로 그냥 값 자체와 개행문자를 계속 추가하여 출력하는 것으로 방식을 바꿨더니 통과가 됐다.

 

약간 의문인 점은 2018년에 올라온 출력 속도 비교 글에서는 BufferedWriter를 사용하는 것이 StringBuilder를 사용하는 것보다 약간 더 빠른 것으로 측정되었다는데 이 문제에서는 오히려 BufferedWriter가 시간 초과를 받고 StringBuilder가 통과되었다. 이 부분은 조금 더 관련 내용을 찾아봐야 할 것 같다.

---

Code

import java.util.StringTokenizer

fun main() = with(System.`in`.bufferedReader()) {
    val sb = StringBuilder()
    var st = StringTokenizer(readLine())
    val n = st.nextToken().toInt()
    val m = st.nextToken().toInt()
    val stations = Subway().apply {
        var prev = 0
        st = StringTokenizer(readLine())
        repeat(n) {
            val temp = st.nextToken().toInt()
            addStation(prev, temp)
            prev = temp
        }
    }
    repeat(m) {
        st = StringTokenizer(readLine())
        val work = st.nextToken()
        val temp = st.nextToken().toInt()
        when (work) {
            "BN" -> {
                sb.append(stations.next[temp]).append('\n')
                stations.addStation(temp, st.nextToken().toInt())
            }
            "BP" -> {
                sb.append(stations.prev[temp]).append('\n')
                stations.addStation(stations.prev[temp], st.nextToken().toInt())
            }
            "CN" -> {
                sb.append(stations.next[temp]).append('\n')
                stations.removeStation(stations.next[temp])
            }
            "CP" -> {
                sb.append(stations.prev[temp]).append('\n')
                stations.removeStation(stations.prev[temp])
            }
        }
    }
    println(sb)
}

class Subway(val prev: IntArray = IntArray(1000001), val next: IntArray = IntArray(1000001)) {
    fun addStation(prev: Int, new: Int) {
        if (prev == 0) {
            this.prev[new] = new.also { next[new] = it }
            return
        }
        this.prev[new] = prev
        next[new] = next[prev]
        this.prev[next[prev]] = new
        next[prev] = new
    }

    fun removeStation(target: Int) {
        prev[next[target]] = prev[target]
        next[prev[target]] = next[target]
    }
}