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

문제

---

생각하기

---

• 이분 탐색 문제이다.
  • lowerBound와 upperBound를 찾아야 한다.
• 좋은 문제인 것 같음

동작

결과

코드

---

Kotlin

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

// input
private lateinit var br: BufferedReader

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

private lateinit var HIArr: IntArray
private lateinit var ARCArr: IntArray

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

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()
    var hiWin = 0L
    var draw = 0L
    var arcWin = 0L

    for (i in 0 until M) {
        val lower = lowerBound(0, N, ARCArr[i])
        val upper = upperBound(0, N, ARCArr[i])
        val d = upper - lower

        draw += d
        hiWin += N - upper
        arcWin += upper - d
    }

    sb.append(hiWin).append(' ').append(arcWin).append(' ').append(draw)
    return sb.toString()
} // End of solve()

private fun lowerBound(low: Int, high: Int, target: Int): Int {
    if (low == high) return low

    val mid = (low + high) / 2
    return if (HIArr[mid] < target) {
        lowerBound(mid + 1, high, target)
    } else lowerBound(low, mid, target)
} // End of lowerBound()

// 찾고자 하는 값 이하의 값 중 가장 큰 값을 갖는 요소의 인덱스 + 1 을 반환
fun upperBound(low: Int, high: Int, target: Int): Int {
    if (low == high) return low

    val mid = (low + high) / 2
    return if (HIArr[mid] <= target) {
        upperBound(mid + 1, high, target)
    } else upperBound(low, mid, target)
} // End of upperBound()

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

    StringTokenizer(br.readLine()).run {
        HIArr = IntArray(N) {
            nextToken().toInt()
        }
    }

    StringTokenizer(br.readLine()).run {
        ARCArr = IntArray(M) {
            nextToken().toInt()
        }
    }

    HIArr.sort()
    //ARCArr.sort()
} // End of input()