[백준] 13334번: 철로

문제링크

• h <= o 라는 조건이 없기 때문에 시작점과 도착점을 통일시켜주기 위해 h <= o 조건을 구현해줍니다.
• 도착점을 기준으로 오름차순 정렬을 합니다.
• 0부터 (n-1)까지 순회를 합니다.
• 최소힙에 시작점을 넣어주고, peek 값이 (현재 도착점 - d) 값보다 작은 경우 모두 pop을 해줍니다.
• 최소힙의 사이즈는 (현재 도착점 - d)에 포함되어 있는 철로의 개수를 의미합니다.

import java.util.*
import kotlin.math.max

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val n = br.readLine().toInt()

    val lines = mutableListOf<Pair<Int, Int>>()
    for (i in 0 until n) {
        var (h, o) = br.readLine().split(" ").map { it.toInt() }
        if (h > o) {
            val temp = h
            h = o
            o = temp
        }
        lines.add(Pair(h, o))
    }
    lines.sortBy { it.second }
    val d = br.readLine().toInt()

    var answer = 0
    val pq = PriorityQueue<Int>(compareBy { it })
    for (i in 0 until n) {
        pq.add(lines[i].first)
        while (pq.isNotEmpty() && pq.peek() < (lines[i].second - d)) pq.poll()
        answer = max(answer, pq.size)
    }
    bw.write("$answer")

    br.close()
    bw.close()
}

시간복잡도

O(n * logn)