[백준][KOTLIN] 2751 수 정렬하기 2

풀이

1. 입력이 1,000,000 이므로 O(N) 시간복잡도가 되어야 한다.
2. Kotlin API 혹은 정렬 알고리즘 중 최대 O(N) 시간 복잡도를 가지는 것을 선택 한다.
3. Kotlin API 의 Arrays.sort() 를 이용할 경우 시간 초과가 발생한다. Collections.sort() 를 이용할 경우 최소 O(NlogN) 에서 최대 O(N) 의 시간 복잡도를 가지게 되어 문제의 조건을 만족한다.
4. 정렬 알고리즘을 이용할 경우 퀵 정렬은 최악의 경우 O(N^2)의 시간 복잡도를 가지므로 이 문제는 합병 정렬을 이용한다.
5. 마지막으로 println 으로 출력시 시간 초과가 발생할 경우 BufferedWriter 로 한번에 출력될 수 있도록 한다.

코드

1. Collections.sort() 이용

import java.io.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    val n = br.readLine().toInt()
    val nums = mutableListOf<Int>()

    repeat(n) {
        nums.add(br.readLine().toInt())
    }

    nums.sort()

    val sb = StringBuilder()

    for (num in nums) {
        sb.append("$num\n")
        //println(num)
    }

    bw.write(sb.toString())
    bw.flush()
    bw.close()
    br.close()
}

 

2. 합병 정렬 알고리즘 이용

import java.io.*

private lateinit var sorted: IntArray

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    val n = br.readLine().toInt()
    sorted = IntArray(n)
    var nums = IntArray(n) {
        br.readLine().toInt()
    }

    mergeSort(nums, 0, nums.size - 1)

    val sb = StringBuilder()
    for (num in nums) {
        sb.append("$num\n")
    }

    bw.write(sb.toString())
    bw.flush()
    bw.close()
    br.close()
}

private fun mergeSort(arr: IntArray, left: Int, right: Int) {
    if (left == right) return

    val mid = (left + right) / 2
    mergeSort(arr, left, mid)
    mergeSort(arr, mid + 1, right)
    merge(arr, left, mid, right)
}

private fun merge(arr: IntArray, left: Int, mid: Int, right: Int) {
    var l = left // 왼쪽 부분 배열의 시작점
    var r = mid + 1 // 오른쪽 부분 배열의 시작점
    var idx = l // sorted 배열의 첫 위치

    while(l <= mid && r <= right) {
        if (arr[l] > arr[r]) {
            sorted[idx++] = arr[r++]
        } else {
            sorted[idx++] = arr[l++]
        }
    }

    // 왼쪽 부분 배열이 없을 경우
    if (l > mid) {
        while (r <= right) {
            sorted[idx++] = arr[r++]
        }
    } else {
        while (l <= mid) {
            sorted[idx++] = arr[l++]
        }
    }

    for (i in left..right) {
        arr[i] = sorted[i]
    }
}