백준 11663번
https://www.acmicpc.net/problem/11663

문제

---

생각하기

---

• 이분 탐색 문제이다.

  • lowerBound와 UpperBound를 찾아야 한다.

• 선분위에 있는 점의 개수는 상한선 - 하한선으로 구할 수 있다.

동작

코드

---

Kotlin

import java.io.*
import java.util.*

// input
private lateinit var br: BufferedReader
private lateinit var st: StringTokenizer

// variables
private var N = 0
private var M = 0

private lateinit var points: IntArray
private lateinit var coordinates: Array<Coordinate>
private var upper = 0
private var lower = 0

private data class Coordinate(var start: Int, var end: Int)


fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    val sb = StringBuilder()

    input()
    points.sort()

    for (i in 0 until M) {
        upper = Int.MIN_VALUE
        lower = Int.MAX_VALUE

        lowerBinarySearch(0, N - 1, coordinates[i].start)
        upperBinarySearch(0, N - 1, coordinates[i].end)

        if (lower <= upper) {
            sb.append(upper - lower + 1).append('\n')
        } else {
            sb.append(0).append('\n')
        }
    }

    bw.write(sb.toString())
    bw.close()
} // End of main

private fun lowerBinarySearch(low: Int, high: Int, target: Int): Int {
    if (low > high) return -1

    val mid = (low + high) / 2
    if (target <= points[mid]) {
        lower = Math.min(lower, mid)
        val temp = lowerBinarySearch(low, mid - 1, target)
        return if (temp == -1) {
            mid
        } else {
            temp
        }
    } else {
        return lowerBinarySearch(mid + 1, high, target)
    }
} // End of lowerBinarySearch

private fun upperBinarySearch(low: Int, high: Int, target: Int): Int {
    if (low > high) return -1

    val mid = (low + high) / 2
    if (target >= points[mid]) {
        upper = Math.max(upper, mid)
        val temp = upperBinarySearch(mid + 1, high, target)
        return if (temp == -1) {
            mid
        } else {
            temp
        }
    } else {
        return upperBinarySearch(low, mid - 1, target)
    }
} // End of upperBinarySearch

private fun input() {
    st = StringTokenizer(br.readLine())
    N = st.nextToken().toInt()
    M = st.nextToken().toInt()

    points = IntArray(N)
    st = StringTokenizer(br.readLine())
    for (i in 0 until N) {
        points[i] = st.nextToken().toInt()
    }

    coordinates = Array(M) { Coordinate(0, 0) }
    for (i in 0 until M) {
        st = StringTokenizer(br.readLine())
        coordinates[i] = Coordinate(st.nextToken().toInt(), st.nextToken().toInt())
    }
} // End of input