[백준] 13334번. 철로(JAVA)

문제

https://www.acmicpc.net/problem/13334

---

풀이(40분)

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

public class Main {

    static final List<Interval> intervals = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int point1 = Integer.parseInt(st.nextToken());
            int point2 = Integer.parseInt(st.nextToken());
            int start = Math.min(point1, point2);
            int end = Math.max(point1, point2);
            intervals.add(new Interval(start, end));
        }

        final int d = Integer.parseInt(br.readLine());

        // 끝점을 기준으로 정렬 (같으면 시작점 오름차순)
        Collections.sort(intervals);

        int maxCount = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>(); // 시작점 오름차순 저장

        for (Interval interval : intervals) {
            int lineEnd = interval.end;
            int lineStart = lineEnd - d;

            pq.offer(interval.start);

            // 선분을 벗어나는 시작점 제거
            while (!pq.isEmpty() && pq.peek() < lineStart) {
                pq.poll();
            }

            maxCount = Math.max(maxCount, pq.size());
        }

        System.out.println(maxCount);
    }

    static class Interval implements Comparable<Interval> {
        int start, end;

        public Interval(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public int compareTo(Interval other) {
            if (this.end != other.end) {
                return this.end - other.end;
            }
            return this.start - other.start;
        }
    }
}

---

문제 풀이 전략

 

슬라이딩 윈도우 + 우선순위 큐를 조합하여 해결한 문제이다.

1. 한 사람을 (start, end) 구간으로 표현
2. 철로는 한 번만 설치 가능 → 어디에 설치할지만 결정하면 됨
3. 철로 범위는 [x, x + d] 형태 → 구간 (start, end)가 이 범위에 완전히 포함되어야 함
4. 모든 사람에 대해 철로를 끝점에 맞춰 설치해보며 최대 인원을 계산

• 구간 (start, end)를 모두 정렬해서 철로의 끝 위치 end를 기준으로 탐색
• end - d 이상인 구간의 start만 남겨서, 철로 안에 완전히 들어오는 사람만 카운트
• 이때, start를 우선순위 큐에 담아, 범위 바깥인 구간은 빠르게 제거