글이 많이 도움이 되었습니다. 실제로 몇몇 문제에서 sortWith을 버리고 객체에 CompareTo를 구현하는 방식으로 정렬할 경우 메모리 초과를 피하는 것 같아요.
코틀린 API의 sort를 구현한 소스를 보면 단순히 자바의 sort를 호출하더군요. (참조 - https://ongveloper.tistory.com...)
그리고 자바의 Collections에 정의된 sort는 merge sort와 insert sort를 혼합한 tim sort를 사용하는 데, 저도 잘 모르지만 merge sort 방식이 메모리에 새로운 버퍼를 의미 있는 수준까지 생성하는 것 같습니다.

emrdbs123 3년 전 3
이 문제의 핵심은 MST 를 구성하는 엣지의 후보군의 공간복잡도를 낮게 가져가는 방식을 찾는것입니다.
단순하게 가능한 모든 Edge 를 때려박으면 n * (n-1) /2 개의 Edge 를 모두 Queue 나 List에 담아야 해서 메모리가 초과 됩니다. (1 % -> 바로 터짐)
(x,y,z) 별로 정렬을 수행하여 인접한 좌표 끼리만 실제 MST 의 Edge 가 될 수 있습니다. (다른 분들 풀이 보고 알았음...)
그래서 3 * (n - 1) 개의 Edge 후보군을 저장하여 정렬을 수행해야합니다.
그런데 이 문제에서 아래와 같은 kotlin 의 정렬 API 를 사용하면 메모리 초과가 발생합니다. (7% 에서 터짐)
/* 터지는 방식들 */
private data class Point(val idx: Int, val value: Int) // 각 (x,y,z) 별 인덱스와 값을 담을 data class val x = mutableListOf() // x 값의 목록을 담을 리스트 /* x 값을 입력 받는다 */ /* case 1 */ x.sortBy { it.value } // 정렬을 한다. -> 터짐 /* case 2 */ x.sortWith(comparaeBy {it.value}) // 위 코드와 같음 -> 터짐 /* case 3 */ val valueComp = comparaeBy {it.value} // comp 를 별도 저장하고 정렬 한다 -> 터짐 x.sortWith(valueComp)이 문제를 해결 하기 위해서는 Point 클래스를 Comparable 을 구현한 형태로 바꾸어 주던가 Comparator 를 생성할때
kotlin 의 compareBy 가 아니라 람다를 이용해 직접 만들어 주어야 합니다.
/* 안 터지는 방식 들 */
/* case 4 */ private data class Point(val idx: Int, val value: Int) : Comparable<Point> { override fun compareTo(other: Point) = value - other.Value } x.sort() // -> comparable 을 이용한 sort 수행 comparator 지정 x /* case 5 */ val valueComp = Comparator<Point> { p1, p2 -> p1.value - p2.value }// comp 를 직접 만든다 (compareBy 사용 x) x.sortWith(valueComp)이게 왜 그런지 하루정도 머리 박으면서 여러 실험을 해보았는데 정확한 이유나 발생 조건을 알아내지는 못했습니다.
(여러 방식으로 머리 박아본 실험 - 깃헙 링크)
실험 해보니 문제가 Kotlin 의 Comparator 생성 API 에서 활용하는 compareValues API 에서 === 비교를 하고 또한 뭔가 타입 이레이져같은게 동작해서 컴파일러가 얘를 객체타입으로 인식해서 각 Primitive Int 를 객체 Integer 로 변환해 힙 메모리에 저장하는거 같긴한데 정확한지는 잘 모르겠습니다.
Queue 로도 실험해보고 다른 여러 방식으로도 실험해 보았는데 확실히 compareValues 얘가 포함된 API 를 사용할때 문제가 발생하기는 합니다.
혹시 이유를 아시는 분은 알려주시면 감사하겠습니다.