baekjoon: 2751. 수 정렬하기 2

문제링크

• 시간제한 : 1초
• N의 범위 : 1 ~ 1,000,000
• O(N^2) : 시간초과
• O(N*logN) : 약 20,000,000

Quick Sort

• 최악의 경우 : O(N^2) -> 시간초과

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun quick(nums: MutableList<Int>, start: Int, end: Int) {
    if (start >= end) return
    val pivot = start
    var i = start + 1
    var j = end
    while (i <= j) {
        while (i <= end && nums[pivot] >= nums[i]) i++
        while (j > start && nums[pivot] <= nums[j]) j--
        if (i > j) {
            val temp = nums[j]
            nums[j] = nums[pivot]
            nums[pivot] = temp
        } else {
            val temp = nums[j]
            nums[j] = nums[i]
            nums[i] = temp
        }
    }
    quick(nums, start, j - 1)
    quick(nums, j + 1, end)
}

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    // n : 1 ~ 1,000,000
    val n = br.readLine().toInt()
    val nums = mutableListOf<Int>()
    for (i in 0 until n) {
        nums.add(br.readLine().toInt())
    }
    quick(nums, 0, n - 1)
    nums.forEach { bw.write("$it\n") }
    br.close()
    bw.close()
}

Merge Sort

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun merge(nums: MutableList<Int>, m: Int, mid: Int, n: Int, sortedArray: Array<Int>) {
    var i = m
    var j = mid + 1
    var k = m
    while (i <= mid && j <= n) {
        if (nums[i] <= nums[j]) sortedArray[k++] = nums[i++]
        else sortedArray[k++] = nums[j++]
    }
    if (i > mid) {
        for (index in j..n) {
            sortedArray[k++] = nums[index]
        }
    } else {
        for (index in i..mid) {
            sortedArray[k++] = nums[index]
        }
    }
    for (index in m..n) {
        nums[index] = sortedArray[index]
    }
}

fun mergeSort(nums: MutableList<Int>, m: Int, n: Int, sortedArray: Array<Int>) {
    if (m < n) {
        val mid = (m + n) / 2
        mergeSort(nums, m, mid, sortedArray)
        mergeSort(nums, mid + 1, n, sortedArray)
        merge(nums, m, mid, n, sortedArray)
    }
}

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    // n : 1 ~ 1,000,000
    val n = br.readLine().toInt()
    val nums = mutableListOf<Int>()
    for (i in 0 until n) {
        nums.add(br.readLine().toInt())
    }
    mergeSort(nums, 0, n - 1, Array(nums.size) { 0 })
    nums.forEach { bw.write("$it\n") }
    br.close()
    bw.close()
}