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

(追記) (追記ここまで)

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

9934번 - 완전 이진 트리

win5649 3년 전 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
}

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

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

win5649 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말