[백준][Kotlin]1300번 K번째 수

해당 문제는 문제를 봤을 때 어떤 알고리즘으로 풀어야하는지 떠오르기부터가 어려운 문제였습니다.

하나 확실했던 것은 문제의 설명 중 "첫째 줄에 배열의 크기 N이 주어진다. N은 10^5보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(10^9, N^2)보다 작거나 같은 자연수이다."  문구가 있어 N^2의 시간복잡도를 가지는 코드는 딱히 확인해 보지 않더라도 시간초과가 나온다는 것을 알 수 있었습니다.

그렇다면 해당 문제는 어떻게 풀어야하는지 생각해 보니 K번째 수는 K보다 클 수 없음을 알 수 있습니다.

1	2	3
2	4	6
3	6	9

 

값	1	2	2	3	3	4	6	6	9
순서	1	2	3	4	5	6	7	8	9

 

이진 탐색을 이용하여 배열에서 mid 값보다 작은 수의 개수를 계산하고, k와 비교하여 탐색 범위를 조절하는 방법으로 k번째 작은 수를 찾을 수 있습니다.

 

우선, 이진 탐색을 위해 시작 범위와 끝 범위를 지정합니다. 시작 범위는 1, 끝 범위는 K로 지정합니다.

그리고 이진 탐색을 수행합니다. 탐색을 반복할 때마다 mid 값을 계산합니다. mid 값은 시작 범위와 끝 범위의 중간값으로 지정됩니다. 배열에서 mid 값보다 작은 값의 개수를 의미합니다.

mid 값을 계산한 후, mid 값보다 작은 값의 개수를 계산합니다. 이때, mid 값을 i로 나눈 몫과 n 중 작은 값을 선택합니다. 이 값은 mid 값보다 작은 수의 개수입니다. 예를 들어, mid 값이 6이라면 i로 나눈 몫은 2이므로 2행에는 6보다 작은 값이 2개 있습니다. 하지만 2행에는 총 n개의 원소가 있으므로, 2행에서 6보다 작은 값은 n개 이상 있을 수 없습니다. 따라서 이 값은 2입니다.

이렇게 mid 값보다 작은 값의 개수를 계산한 후, k와 비교합니다. k가 mid 값보다 작다면 끝 범위를 mid-1로 수정하고, k가 mid 값보다 크다면 시작 범위를 mid+1로 수정합니다.

 

하기는 제가 작성한 코드와 제출 결과 입니다.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.lang.Math.max
import java.util.*

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    //var bw = BufferedWriter(OutputStreamWriter(System.out))
    var st = StringTokenizer(br.readLine())
    val N = st.nextToken().toInt()
    st = StringTokenizer(br.readLine())
    val K = st.nextToken().toInt()

    var start = 1
    var end = K
    var answer = 0
    while(start <= end){
        var count = 0
        var mid = (start+end)/2

        for(i in 1 .. N){
            count += Math.min(mid/i,N) // 해당 부분은 1의 경우 index를 초과하는 부분이 있음.
            //따라서 mid/i가 N을 벗어난다면 N 입력
        }

        if(count < K){
            start = mid +1
        }
        if(count >= K){
            end = mid-1
        }
    }

    println(start)

    //bw.flush()
    //bw.close()
}