[백준 13334] 철로 (Kotlin)

🏆 문제 난이도
- Gold II

🔗 문제 링크
https://www.acmicpc.net/problem/13334

📝 문제 분석 & 접근

처음 문제를 접하면 모든 사람의 집과 회사 위치를 탐색해야 할 것 같아서 복잡하게 느껴질 수 있습니다.

하지만 잘 생각해 보면, 기차 경로는 시작점과 끝점 사이의 거리가 d 이하인 모든 구간을 의미합니다.

즉, [기차의 시작점, 기차의 시작점+d] 구간을 검사하면 되는 것입니다.

 

우리는 이 기차 구간 안에 최대한 많은 사람이 포함되도록 해야 합니다.

한 사람이 기차에 타려면, 그 사람의 집과 회사 위치가 모두 이 구간 안에 포함되어야 합니다.

---

✨ 핵심 아이디어

단순히 1부터 끝까지 모든 구간을 하나씩 검사하는 것은 오랜 시간이 걸립니다.

따라서 아래같은 약간의 트릭이 필요합니다.

 

• 정렬 (Sorting)
  • 모든 사람의 집과 회사 위치 중 회사 위치 (to)를 기준으로 오름차순 정렬합니다.
  • 하단 코드의 list.sortBy { it.to } 이 부분이 이 아이디어에 해당됩니다.
  • 회사 위치로 정렬하는 이유는, 차의 끝 지점(오른쪽 끝)이 이 회사 위치에 맞춰서 순차적으로 이동한다고 생각하면 편하기 때문입니다.
  • 기차의 끝 지점이 오른쪽으로 쭉 움직이면서, 그 시점에 태울 수 있는 사람들을 확인하는 거라고 생각해도 됩니다.
• 우선순위 큐 (Priority Queue)
  • 이제 기차의 끝 지점을 기준으로 사람들을 한 명씩 보면서, 현재 구간에 태울 수 있는 사람들을 PriorityQueue에 넣어 관리해줍니다.
  • PriorityQueue의 핵심은 가장 작은 값(집 위치)을 우선적으로 꺼내오도록 설정하는 겁니다.
  • 코드에서는 compareBy { it.from } 이 부분입니다.

 

코드 플로우를 글로 펼쳐보면,

 

1. 회사 위치를 기준으로 정렬된 사람 리스트를 순회합니다.
2. 각 사람을 순회할 때마다, 그 사람의 정보를 PriorityQueue에 추가합니다. 이 사람은 현재 기차의 끝 지점(자신의 회사 위치)에 포함될 자격이 생긴 거라고 생각하면 됩니다.
3. PriorityQueue에 들어있는 사람들은 기차에 탈 가능성이 있는 사람들입니다. 하지만, 기차의 시작점(왼쪽 끝)은 현재 사람의 회사 위치 - d보다 작을 수 없습니다. 따라서 while(pq.peek().from < node.to - d) 코드를 통해 기차 구간을 벗어나는 사람들을 PriorityQueue에서 제거해줍니다.
4. 이 과정을 거치면, PriorityQueue에는 현재 기차 구간 안에 포함된 사람들만 남게 되고, 이때 PriorityQueue의 크기(pq.size)가 현재 기차 구간에 탑승한 사람의 수가 됩니다. 이 값을 최대값(ans)과 비교하여 계속 갱신하면 됩니다.

 

---

💻 코드

import java.io.StreamTokenizer
import java.util.PriorityQueue
import kotlin.math.max

data class Node(
    var from: Int,
    var to: Int,
) {
    init {
        if (from > to) {
            from = to.also { to = from }
        }
    }
}

fun main() = with(StreamTokenizer(System.`in`.bufferedReader())) {
    fun StreamTokenizer.nextInt(): Int{
        nextToken()
        return nval.toInt()
    }

    val n = nextInt()
    val list = mutableListOf<Node>()
    repeat(n) {
        list.add(Node(nextInt(), nextInt()))
    }
    list.sortBy { it.to }

    val d = nextInt()

    val pq = PriorityQueue<Node>(compareBy { it.from })
    var ans = 0
    for(node in list) {
        pq.add(node)
        while(pq.isNotEmpty() && pq.peek().from < node.to - d) pq.poll()
        ans = max(ans, pq.size)
    }
    println(ans)
}