[BOJ 13334 - 철로]

BOJ 13334 - 철로

이제는 자바로 알고리즘 문제를 푸는 것이 많이 능숙해졌다.
오히려 c++로 어떻게 풀었는지 가물가물할 정도?

수직선 위의 여러 선분 들 중, 길이가 d인 임의의 선분 L 안에 포함되는 선분의 개수의 최댓값을 찾는 문제이다.

수직선의 좌표는 -10억 ~ 10억 이므로 좌표를 배열로 만드는 접근은 불가능하다.

접근 방법

임의의 선분 L을 좌에서 우로 이동하며 각각의 지점에서 포함되는 선분의 개수를 파악하여, 최댓값을 그때마다 갱신해야한다.

하지만 수직선의 좌표가 20억 가량 존재하므로 하나씩 옮기는 것은 불가능하다.

즉, 포함되는 선분의 개수가 바뀔 가능성이 있는 지점(변곡점)만을 파악해야하고,
이는 각각의 선분(hi, oi)에 대해 oi 인 지점들일 것이다. (단, hi <= oi)

oi 지점들을 전부 순회하는 것은 O(N)이고, N의 최댓값이 100,000 이므로, 각각의 지점들에서 포함되는 선분을 파악하는 연산은 O(log N) 이하로 처리해야한다.
이때 전체 시간복잡도는 O(N log N)이 되며 주어진 시간 안에 통과가 가능하다.

각각의 지점들에서 포함되는 선분을 파악하는 연산을 어떻게 O(log N) 이하로 처리할 것인가?

O(log N) 하면 바로 떠오르는 것이 트리 자료구조 아닌가?

포인트는 임의의 선분 L을 옆으로 쭉 이동하면서,
이전에 포함되었던 선분의 정보를 저장해 놓는 것이다.

이때 heap 자료구조에 저장을 해놓고, 조건에 부합하지 않는 선분은 삭제하는 식으로 문제를 해결하였다.

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;

public class Main {

    static class Line {
        int small;
        int big;

        public Line(int small, int big) {
            this.small = small;
            this.big = big;
        }
    }

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

        Set<Line> lines = new HashSet<>();

        for(int i = 0; i < humans; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            Line line = new Line(Math.min(a, b), Math.max(a, b));
            lines.add(line);
        }
        int railLength = Integer.parseInt(br.readLine());

        List<Line> orderByBig = lines.stream()
                .filter(l -> l.big - l.small <= railLength)
                .sorted(Comparator.comparingInt(l -> l.big))
                .collect(Collectors.toList());

        PriorityQueue<Line> pq = new PriorityQueue<>(Comparator.comparingInt(l -> l.small));

        int maxValue = 0;

        for (Line line : orderByBig) {
            pq.add(line);
            while(!pq.isEmpty() && pq.peek().small < line.big - railLength) {
                pq.poll();
            }
            maxValue = Math.max(maxValue, pq.size());
        }

        System.out.println(maxValue);
    }
}