글 읽기 - [Kotlin / Java] 시간초과 어떻게 해결할까요 ㅠㅠ?

linear114 3년 전 0

제가 배운 선에서 QuickSort를 이용해서 구현을 해보았습니다...

그리고 이곳저곳에서 얻은 힌트를 가지고

더 이상 정렬하지 않아도 될 부분에서는 QuickSort를 추가적으로 돌리지 않았습니다.

어떻게 시간을 더 단축시킬 수 있을까요?

1년전에도 시간초과때문에 포기했던 문제인데,

또 다시 시간초과의 늪에서 벗어나지를 못해 갑갑한 심정입니다 ㅠㅠ

import java.io.BufferedWriter
import java.io.OutputStreamWriter

fun main() {
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    val (n, k) = readLine()!!.split(" ").map{ it.toInt() }
    val array = readLine()!!.split(" ").map{ it.toInt() }.toIntArray()

    fun quickSort(start: Int, end: Int) {
        if(start >= end) return

        val pivot = array[start]
        var largerIndex = start + 1
        var smallerIndex = end

        while(smallerIndex >= largerIndex) {
            while(largerIndex <= end && pivot >= array[largerIndex]) {
                largerIndex++
            }
            while(smallerIndex >= start && pivot < array[smallerIndex]) {
                smallerIndex--
            }

            if(largerIndex <= smallerIndex) {
                val temp = array[largerIndex]
                array[largerIndex] = array[smallerIndex]
                array[smallerIndex] = temp
            } else {
                val temp = array[start]
                array[start] = array[smallerIndex]
                array[smallerIndex] = temp
            }
        }

        if (k-1 in start until smallerIndex) {
            quickSort(start, smallerIndex - 1)
        } else if(k-1 in smallerIndex + 1 .. end) {
            quickSort(smallerIndex + 1, end)
        }
    }

    quickSort(0, n-1)
    bw.write(array[k-1].toString())
    bw.flush()
}

ckdgus2482 3년 전 0

k-1이 smallerIndex와 같아졌을때도 재귀호출이 발생하는 것 같습니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[Kotlin / Java] 시간초과 어떻게 해결할까요 ㅠㅠ?

linear114 3년 전 0

ckdgus2482 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말