Kotlin] 백준 2346번 문제풀이

https://www.acmicpc.net/problem/2346

2346번: 풍선 터뜨리기

 

이 문제 코틀린에게는 너무.. 너무 가혹한 문제입니다.

메모리 제한이 4mb거든요. 

(근데 모든 값을 int라고 해도 위치 인덱스와 종이에 쓰인 숫자를 모두 int 형으로 받는다고 해도 총합이 16,000byte인데 이게 크게 작용하는지는 모르겠습니다.)

코틀린의 큐와 덱은 Linkedlist와 ArrayDeque를 쓰는 것이 일반적이지만 진짜 별의 별 동고쇼를 해봐도 메모리 초과가 납니다.

 

-- 메모리 초과 된 코드 예시--

fun question2346() {
    val count = readln().toInt()
    // Pair<순서, 쪽지 숫자>
    val deque = ArrayDeque<Pair<Int, Int>>()
    val balloons = readln().split(" ").map { it.toInt() }

    for (i in 1 .. count) {
        deque.add(Pair(i, balloons[i - 1]))
    }

    val stringBuilder = StringBuilder()

    val firstShot = deque.removeFirst()
    stringBuilder.append("${firstShot.first} ")
    var note = firstShot.second
    var countBalloons = 0

    while (deque.isNotEmpty()) {
        if(note > 0) {
            countBalloons += 1
            if(countBalloons != note) {
                deque.add(deque.removeFirst())
            } else {
                val shot = deque.removeFirst()
                stringBuilder.append("${shot.first}" )
                note = shot.second
                countBalloons = 0
            }
        } else {
            countBalloons -= 1
            if(countBalloons != note) {
                deque.addFirst(deque.removeLast())
            } else {
                val shot = deque.removeLast()
                stringBuilder.append("${shot.first}" )
                note = shot.second
                countBalloons = 0
            }
        }
    }

    println(stringBuilder.toString().trim())

}

 

LinkedList의 경우 해당 값에 접근할 수 있는 메모리의 address를 저장해서 메모리가 커지고 ArrayDeque는 배열을 사용하기 때문에 초반에 덱을 선언할때 필요한 배열보다 더 크게 선언합니다. 그렇다보니 빡빡한 메모리제한에서 걸리는것 같습니다.. 그래서 스텍 큐 대신 유사하게 사용할 수 있는 일반 mutableList를 이용하여 풀었습니다.. 

 

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))

    val count = br.readLine().toInt()
    val deque = mutableListOf<Balloon>()
    val st = StringTokenizer(br.readLine())
    var i = 1
    while (st.hasMoreTokens()) {
        val item = st.nextToken().toInt()
        deque.add(Balloon(i, item))
        i++
    }

    var note = 0
    var countBalloons = 0

    val result = mutableListOf<Int>()

    while (deque.isNotEmpty()) {

        // 무조건 처음임~
        if (note == 0) {
            deque.removeFirst().apply {
                result.add(this.index)
                note = this.note
            }
        } else if (note > 0) {
            countBalloons += 1
            if (countBalloons != note) {
                deque.add(deque.removeFirst())
            } else {
                deque.removeFirst().apply {
                    result.add(this.index)
                    note = this.note
                    countBalloons = 0
                }
            }
        } else {
            countBalloons -= 1
            if (countBalloons != note) {
                deque.add(0, deque.removeLast())
            } else {
                deque.removeLast().apply {
                    result.add(this.index)
                    note = this.note
                    countBalloons = 0
                }
            }
        }
    }


    println(result.joinToString(" "))
}

data class Balloon(
    val index: Int,
    val note: Int
)

 

(메모리 초과를 탈출하기 위한 몸부림)