백준 11663 선분 위의 점 Kotlin (이분 탐색)

문제 출처 : https://www.acmicpc.net/problem/11663

11663번: 선분 위의 점

문제

일차원 좌표상의 점 N개와 선분 M개가 주어진다. 이때, 각각의 선분 위에 입력으로 주어진 점이 몇 개 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 끝점이 주어진다. 입력으로 주어지는 모든 좌표는 1,000,000,000보다 작거나 같은 자연수이다.

출력

입력으로 주어진 각각의 선분 마다, 선분 위에 입력으로 주어진 점이 몇 개 있는지 출력한다.

알고리즘 분류

• 정렬
• 이분 탐색

풀이

간만에 이분 탐색 연습하려고 푼 문제이다.

이분 탐색은 아직도 짤 때마다 값이 정확히 나오는지 확인하곤 한다.

 

우선 선분의 최대 길이가 10억이기 때문에, 10억짜리 선분의 start와 end를 선형으로 탐색하면 선분 하나만 확인해도

시간 초과이다. 따라서 이분 탐색을 통해 O(10만 * 10억)의 시간 복잡도를 O(10만 * log10억)으로 줄여야 통과할 수 있다

일단 이분 탐색을 리스트의 값들이 정렬되어있어야 하기도 하고, 문제에선 주어진 점들을 오름차순으로 정렬해놓는다면,

선분의 시작점을 s 끝을 e라고 할 때,  리스트에서 s가 위치하는 인덱스와 e가 위치하는 인덱스를 구해서 e-s를 한다면 선분 안에 있는 점들의 수를 쉽게 구할 수 있다.

 

오랜만에 그림을 또 그려본다.

위 그림에서 2와 15의 인덱스는 1, 15의 인덱스는 3이 된다.

즉 3-1로 안에 있는 점의 수 2가 나온다.

 

선분 (3, 30)은 어떨까?

3의 인덱스는 1, 30의 인덱스는 4이다.

어라? 4-1은 3인데 실제 선분에는 4개의 점이 있다.

이런 경우(선분의 끝(e)이 점과 겹치는 경우)는 e를 1늘려주면 된다.

 

c++에선 lower_bound와 upper_bound로 쉽게 구할 수 있다.

그리고 재귀로 짠 이분 탐색보다 그냥 while문으로 짠 이분 탐색이 더 성능이 좋다.

실제로 재귀로 짰다가 스택오버플로우가 난 적이 있다.

시간초과였나?

그래도 함수가 더 이쁘지 아니한가.

코드

val br = System.`in`.bufferedReader()

lateinit var set : List<Int>

fun biSearch(start : Int, end : Int, findVal : Int) : Int{

    if(start>=end){
        return start
    }
    val mid = (start+end)/2

    return if(set[mid]==findVal){
        mid
    }
    else if(set[mid]<findVal){
        biSearch(mid+1,end,findVal)
    }
    else{
        biSearch(start,mid,findVal)
    }
}

fun main() = with(System.out.bufferedWriter()){

    val (n,m) = br.readLine().split(' ').map{it.toInt()}
    set = br.readLine().split(' ').map{it.toInt()}.sorted()
    for(i in 0 until m){
        val (left,right) = br.readLine().split(' ').map{it.toInt()}

        val start = biSearch(0,n,left)
        var end = biSearch(0,n,right)

        if( end < n &&  right==set[end]){
            end++
        }
        write("${end-start}\n")
    }

    close()
}