글 읽기 - BFS 로 풀었을 때 메모리 초과가 나는 이유가 뭘까요?

win5649 1년 전 0

이진탐색을 BFS 로 구현하였습니다

k 가 최대 10까지 가능하여서 2^10 만큼 공간을 사용하는데

큐에 넣고 뺄떄도 중복이 가능하지 않아서 잘 동작할 줄 알았는데

메모리 초과가 발생하네요 문제의 맥시멈이 128MB 인데 왜 그런지 궁금합니다...

import java.util.*
import kotlin.math.max
import kotlin.math.pow
import kotlin.math.sqrt

fun main() {
    with(System.`in`.bufferedReader()) {
        val k = readLine().toInt()

        val cityNumbers = readLine().split(" ").map { it.toInt() }

        val disposedCities = getDisposedCities(cityNumbers)

        val sb = StringBuilder()

        for (i in 0..sqrt(cityNumbers.size.toDouble()).toInt()) {
            for (k in 0 until 2.0.pow(i).toInt()) {
                sb.append("${disposedCities.poll()} ")
            }
            sb.append("\n")
        }

        print(sb)
    }
}

fun getDisposedCities(
    cityNumbers: List<Int>,
): LinkedList<Int> {
    val disposedCities = LinkedList<Int>()
    val queue = LinkedList(listOf(0 to cityNumbers.size - 1))

    while (queue.isNotEmpty()) {
        val (left, right) = queue.poll()

        val mid = (left + right) / 2
        disposedCities.add(cityNumbers[mid])

        if (left <= mid - 1) {
            queue.add(left to mid - 1)
        }
        if (mid + 1 <= right) {
            queue.add(mid + 1 to right)
        }

    }
    return disposedCities
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

BFS 로 풀었을 때 메모리 초과가 나는 이유가 뭘까요?

win5649 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말