문제풀이
- 이분 탐색을 통해 각 딸기가 어떤 영역에 속해 있는지 구분한다.
- HashMap에 각 딸기의 영역을 저장하고 최대, 최소값을 구한다.
주의사항
- 딸기가 존재하는 영역이 전체 영역의 개수보다 작으면 최소값이 0이다.
소요시간
20분
package AtCoder.ProblemList.Difficulty800_1199.APieceofCake
fun main() {
val (W, H) = readln().trim().split(" ").map(String::toInt)
val N = readln().trim().toInt()
val posList = List(N) { readln().trim().split(" ").map(String::toInt) }
val A = readln().trim().toInt()
val aList = ("0 " + readln().trim()).split(" ").map(String::toInt).sorted()
val B = readln().trim().toInt()
val bList = ("0 " + readln().trim()).split(" ").map(String::toInt).sorted()
val map = mutableMapOf<Pair<Int, Int>, Int>()
for ((x, y) in posList) {
val i = aList.binarySearch(x).let { if (it >= 0) it else -it - 1 }
val j = bList.binarySearch(y).let { if (it >= 0) it else -it - 1 }
map.compute(i to j) { _, v -> if (v == null) 1 else v + 1 }
}
val min = if ((A + 1).toLong() * (B + 1) > map.size) 0 else map.values.min()
val max = map.values.max()
println("$min $max")
}