2751번 수 정렬하기

선택정렬 알고리즘이라고 생각하고 가벼운마음으로 도전했다가 시간초과에 호되게 당했다..

퀵정렬 알고리즘..?

문제

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

코드

---

시간초과 발생 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer

fun main() {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val sb = StringBuilder()

    val count= reader.readLine().toInt()
    val emptyArray:IntArray= IntArray(count)
    var temp=0
    for(i in 0 until count){
        emptyArray[i]= reader.readLine().toInt()
    }
    reader.close()
    for(i in 0 until count){
        for(j in i+1 until count) {
            if (emptyArray[i] > emptyArray[j]) {
                temp = emptyArray[i]
                emptyArray[i] = emptyArray[j]
                emptyArray[j]=temp
            }
        }
    }
    for(i in 0 until count){
        sb.append(emptyArray[i]).append('\\n')
    }
    println(sb)
}

빠른 입출력을 위해

val reader = BufferedReader(InputStreamReader(System.*`in`*))

val sb = StringBuilder()

를 모두 이용했지만 시간초과를 피할 수는 없었다..

시간초과2

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.Scanner
fun main() {
    val scanner = Scanner(System.`in`)
    val sb = StringBuilder()

    val count= scanner.nextInt()
    val emptyArray:IntArray= IntArray(count)
    var temp=0
    for(i in 0 until count){
        emptyArray[i]= scanner.nextInt()
    }
    scanner.close()
    for(i in 0 until count){
        for(j in i+1 until count) {
            if (emptyArray[i] > emptyArray[j]) {
                temp = emptyArray[i]
                emptyArray[i] = emptyArray[j]
                emptyArray[j]=temp
            }
        }
    }
    for(i in 0 until count){
        sb.append(emptyArray[i]).append('\\n')
    }
    println(sb)
}

더 빠른 입력을위해

import java.util.Scanner

를 사용해봤지만.. 여전히 시간 초과에 걸리고 말았다..

해결

import java.util.*

fun main() {
    val scanner = Scanner(System.`in`)
    val sb = StringBuilder()
    val count = readLine()!!.toInt()
    val emptyArray = IntArray(count)
    for (i in 0 until count) {
        emptyArray[i] = readLine()!!.toInt()
    }
    scanner.close()

    quickSort(emptyArray, 0, count - 1)

    for (i in 0 until count) {
        sb.append(emptyArray[i]).append('\\n')
    }
    println(sb)
}

fun quickSort(arr: IntArray, left: Int, right: Int) {
    if (left < right) {
        val pivotIndex = partition(arr, left, right)
        quickSort(arr, left, pivotIndex - 1)
        quickSort(arr, pivotIndex + 1, right)
    }
}

//파티션을 랜덤으로~
fun partition(arr: IntArray, left: Int, right: Int): Int {
    val random = Random()
    val randomIndex = random.nextInt(right - left + 1) + left
    swap(arr, randomIndex, right)
    val pivot = arr[right]
    var i = left - 1

    for (j in left until right) {
        if (arr[j] <= pivot) {
            i++
            swap(arr, i, j)
        }
    }

    swap(arr, i + 1, right)
    return i + 1
}

fun swap(arr: IntArray, i: Int, j: Int) {
    val temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

결국 답은 퀵정렬이다.. 사실 퀵정렬을 잘 몰라서 지피티와 구글링을 통해 해결했다.

하지만 퀵정렬을 사용해도 처음에는 시간초과가 발생했다. 퀵정렬에서 피벗 선택을 랜덤하게 하도록 수정하니 문제가 해결되었다..

기존 퀵정렬의 partition 함수에서 피벗으로 사용할 랜덤한 인덱스를 선택하고 해당 인덱스와 배열의 마지막 요소를 교환하는 부분이 추가되었다.

 

퀵정렬 알고리즘

https://youtu.be/cWH49IKDIiI