[백준] 2751번: 수 정렬하기 2 - Kotlin[코틀린]

문제

 

2751번: 수 정렬하기 2

 

---

풀이

 

 먼저 퀵 정렬로 구현하였다가 시간 초과로 실패하였다. 해결 방법을 찾던 중에 https://www.acmicpc.net/board/view/31887 이 공지글을 보았고, 이 문제를 풀기 전에 먼저 읽어보는 것을 추천한다.

 

 이 문제는 시간 복잡도가 O(NlogN)인 정렬인 병합정렬이나 힙 정렬, 기수 정렬, 카운팅 정렬을 사용해야한다. 버블 정렬, 선택 정렬, 삽입 정렬 등은 시간 복잡도가 O(N^2)이므로 시간 초과한다. 퀵 정렬은 평범하게 구현한다면, 시간복잡도가 평균적으로는 O(NlogN)이지만 최악의 경우(이미 정렬이 되어 있거나 역정렬)에는 O(N^2)이 되어서 실패할 수 있다. 이를 회피하는 방법으로 피벗으로 중앙값의 중앙값 고르기, 재귀가 깊어지면 다른 정렬을 사용하기, 랜덤으로 섞은 뒤에 수행하기가 있지만 정교하게 구현하지 않으면 효율이 좋지 않다고 한다. 공지글에서 병합 정렬을 추천해줘서 병합 정렬로 구현해보았다.

 

 병합 정렬은 배열을 분할할 수 없을 때까지 분할하고나서 그 원소들을 병합하면서 정렬해나가는 방식이다. 재귀함수와 분할정복 기법을 이용하는 것이다. 분할 정복이란 하나의 문제를 2개의 문제로 분리하고 각각 해결한 다음, 결과를 모아 원래의 문제를 해결하는 전략이다. 아래의 gif를 보면 병합정렬을 더 이해하기 쉽다.

이미지 출처 - 위키 백과

 

---

코드

 

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val num = br.readLine().toInt()
    val arr = IntArray(num) { br.readLine().toInt() }

    mergeSort(arr, 0, num - 1)

    arr.forEach {
        bw.append("$it\n")
    }

    bw.write("")
    bw.flush()
    bw.close()
    br.close()
}

fun mergeSort(data: IntArray, start: Int, end: Int) {
    if(start>=end) return

    val mid = (start+end)/2 // 배열을 반으로 분할

    mergeSort(data, start, mid) // 재귀
    mergeSort(data, mid + 1, end) // 재귀

    merge(data, start, mid, end) // 분할된 두 배열 병합
}

val tmp = IntArray(1000000) // 정렬될 배열

fun merge(data: IntArray, start: Int, mid: Int, end: Int) {
    var leftStart = start // 왼쪽 배열 인덱스
    var rightStart = mid + 1 // 오른쪽 배열 인덱스
    var idx = start // 정렬될 배열의 인덱스

    while (leftStart <= mid && rightStart <= end) { // 두 배열 중 한쪽을 새로운 배열에 담을 수 없으면 종료
        // 둘 중 최솟값을 배열에 담아줌
        if (data[leftStart] > data[rightStart]) {
            tmp[idx++] = data[rightStart]
            rightStart++
        } else if (data[leftStart] <= data[rightStart]) {
            tmp[idx++] = data[leftStart]
            leftStart++
        }
    }

    if (leftStart > mid) { // 오른쪽 배열 원소가 남아 있는 경우
        for (i in rightStart..end) {
            tmp[idx++] = data[i]
        }
    }

    if (rightStart > end) { // 왼쪽 배열의 원소가 남아 있는 경우
        for (i in leftStart..mid) {
            tmp[idx++] = data[i]
        }
    }

    for (i in start..end) { // 원래의 배열에 대입
        data[i] = tmp[i]
    }
}