[백준] 24511번: queuestack - Kotlin[코틀린]

문제

 

24511번: queuestack

 

---

풀이

 

 처음에는 리스트를 이용해 큐스택을 직접 구현하여 해결하려 했지만, 당연하게도 시간 초과가 발생했다. 모든 요소에서 계산을 처리하면 시간복잡도가 O(NxM)이 되는데, 문제에서 주어진 범위에 따라 N = 10만, M이 10만일 때는 100억의 계산이 필요하기 때문이다.

 

 대신 큐와 스택의 특성을 이용해 계산하는 방법을 생각해 보아야한다. 먼저 스택은 현재 삽입된 원소가 다시 pop되는 것이기 때문에 계산에서 생략할 수 있다. 예를 들어 스택이 [2]인 상태일 때, 3이 삽입되면 스택은 [3]인 상태가 되고 pop을 수행하면 [2]가 된다. 따라서 입력받은 큐스택에서 스택인 수들은 없는 수라고 생각해도 된다.

 

 큐에서는 현재 상태의 원소가 pop되고, 삽입된 원소가 다시 현재 상태의 원소가 된다. 큐스택에서 현재 큐에 있는 원소는 뒤에 있는 큐로 넘어간다. 마지막 큐에 있는 원소가 큐스택의 리턴 값이 되는 것이다. 따라서 이 큐들은 하나의 연결된 큐로 생각할 수 있다. 새로 삽입된 값들도 하나의 큐에 추가하는 값이며, 삽입된 만큼 pop 연산을 수행하여 출력하면 된다. 이렇게 처리하면 시간복잡도는 O(N+M)이 된다.

 

예제 입력 1의 계산은 다음과 같다.

삽입 값	상태	리턴 값
초기	[1, 2, 3, 4]
2	[2, 2, 3, 1]	4
4	[4, 2, 3, 2]	1
7	[7, 2, 3, 4]	2

 

---

코드

 

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val num = br.readLine().toInt()
    val mode = br.readLine().split(' ').map { it.toInt() }
    val queueStack = br.readLine().split(' ').map { it.toInt() }
    var m = br.readLine().toInt()
    val insert = br.readLine().split(' ').map { it.toInt() }

    val sb = StringBuilder()
    for(i in num - 1 downTo 0) { // 마지막 큐부터 출력
        if(m == 0) break // 삽입된만큼 출력하면 종료
        if(mode[i] == 0) { // 큐
            sb.append("${queueStack[i]} ")
            m--
        }
    }
    for(i in insert.indices) { // 삽입된 원소 출력
        if(m == 0) break
        sb.append("${insert[i]} ")
        m--
    }

    bw.write(sb.toString())
    bw.flush()
    bw.close()
    br.close()
}