[백준 알고리즘/Kotlin] 2751번 수 정렬하기2 (feat. 코드 비교하기)

 

문제
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다.
둘째 줄부터 N개의 줄에는 수가 주어진다.
이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다.
수는 중복되지 않는다.

출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1 
5
5
4
3
2
1

예제 출력 1 
1
2
3
4
5

 

 

제출한 2개의 코드를 확인해보며, 두 코드를 비교하도록 하겠습니다.

 

최초 제출 코드 (1번)

import java.lang.StringBuilder
import java.util.PriorityQueue

fun main() = System.`in`.bufferedReader().use { br ->
    val n = br.readLine().toInt()
    val pq = PriorityQueue<Int>()
    val result = StringBuilder()

    repeat(n) {
        val m = br.readLine().toInt()
        pq.add(m)
    }

    while (pq.isNotEmpty()) {
        result.append(pq.poll()).append("\n")
    }

    println(result)
}

메모리 사용량
PriorityQueue는 내부적으로 트리 구조를 가지며, 각 노드는 객체를 참조하고 있습니다.
따라서 메모리 사용량은 입력되는 데이터의 개수에 비례합니다. n개의 데이터를 저장할 때, 메모리는 O(n)이 필요합니다.

시간 복잡도
PriorityQueue는 데이터를 삽입하거나 삭제할 때 log(n)의 시간 복잡도를 가집니다.
따라서 n개의 데이터를 삽입하고 삭제하는데 걸리는 시간 복잡도는 O(n log n)입니다.

 

 

최종 제출 코드 (2번)

import java.lang.StringBuilder

fun main() = System.`in`.bufferedReader().use { br ->
    val n = br.readLine().toInt()
    val list = BooleanArray(2_000_001)
    val result = StringBuilder()

    repeat(n) {
        val m = br.readLine().toInt()
        list[m + 1_000_000] = true
    }

    for (i in list.indices) {
        if (list[i]) {
            result.append(i-1_000_000).append("\n")
        }
    }

    println(result)
}

메모리 사용량
BooleanArray는 fixed-size이며 모든 요소를 메모리에 저장합니다.
따라서 BooleanArray의 크기에 따라 메모리 사용량이 결정됩니다.
이 코드에서는 2_000_001 크기의 BooleanArray를 사용하므로, 메모리 사용량은 O(1)입니다.

시간 복잡도
BooleanArray에 데이터를 삽입하거나 검색하는 작업은 O(1)의 시간 복잡도를 가집니다.
하지만 이 코드에서는 배열의 모든 요소를 순회하므로, 시간 복잡도는 O(n)입니다.

 

즉, PriorityQueue를 사용한 첫 번째 코드는 입력 데이터의 크기에 따라 메모리 사용량과 시간 복잡도가 증가하는 반면,

BooleanArray를 사용한 두 번째 코드는 메모리 사용량은 고정되어 있지만 시간 복잡도는 데이터의 크기에 비례합니다.

 

 

메모리 사용량과 계산 시간

PriorityQueue를 사용한 첫 번째 코드는 PriorityQueue의 특성상 메모리 사용량이 더 많고,
데이터의 삽입과 삭제 과정에서 힙 구조를 유지하기 위해 추가적인 시간이 소요됩니다.
따라서 메모리 사용량이 더 많고 계산 시간이 더 길게 나옵니다.

반면에 BooleanArray를 사용한 두 번째 코드는 메모리 사용량은 더 적지만,
데이터의 삽입과 검색이 O(1)의 시간 복잡도를 가지므로 계산 시간이 더 짧게 나옵니다.

 

따라서, 이 두 코드를 비교하면

BooleanArray를 사용한 두 번째 코드가 메모리 사용량과 계산 시간 모두에서 더 효율적인 것을 확인할 수 있습니다.

 

그러나 이것은 주어진 케이스에 한정된 결과이기 때문에,

사용하는 데이터의 크기나 종류에 따라 결과는 달라질 수 있다고 생각합니다 😊

(크게 동요하지는 않겠으나, 다른 분들의 코드와 함께 살펴보면 좋을 것 같네요 👍🏻)