문제

풀이 과정

요약

힙정렬 응용 문제. 우선순위큐를 활용하였다.

상세

1. 입력값을 받아 우선순위큐 $pq1$ 에 먼저 넣어주었다. 모든 입력 좌표를 확인하되, 도착점을 기준으로 가까운 순으로 살펴보기 위함이다.

   • 입력 값에 출발지와 도착지가 제시되어있지 않으므로, 두 값을 비교하여 큰 값이 도착지로 가게 했다.

2. 모든 좌표를 확인한다. 확인방법은 다음과 같다.

   • 먼저 철로의 길이 $d$ 보다 긴 통근거리는 철로에 포함될 수 없다. $ed-st > d$

   • 도착지를 저장하는 $pq2$ 를 생성하였다. 만약 현재 좌표의 도착점을 $n$이라 한다면 $pq2$ 에는 $n$ 에서 철로의 길이를 뺀것보다 더 큰 값만 있어야 철로에 포함된다 할 수 있다.

   • 만약 조건이 성립하는 경우가 등장한다면 그 이후 출발값들은 이미 성립이 시작한 출발값보다 크므로 모두 포함된다 할 수 있다. 따라서 이때 반복문을 빠져나온다.

   • 매 좌표를 반복하며 현재 $ans$ 값과 $pq2$ 의 갯수와 비교하며 포함될 수 있는 최댓값을 찾는다.

정답

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk;
        int N = Integer.parseInt(br.readLine());

        PriorityQueue<int[]> pq1 = new PriorityQueue<>((n1, n2) -> n1[1] == n2[1] ? n1[0] - n2[0] : n1[1] - n2[1]);
        for (int i = 0; i < N; i++) {
            stk = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(stk.nextToken());
            int n2 = Integer.parseInt(stk.nextToken());
            pq1.add(n1 <= n2 ? new int[]{n1, n2} : new int[]{n2, n1});
        }

        int d = Integer.parseInt(br.readLine());
        int ans = 0;
        PriorityQueue<Integer> pq2 = new PriorityQueue<>();
        while (!pq1.isEmpty()) {
            int[] curr = pq1.poll();
            if (curr[1] - curr[0] > d) continue;
            else pq2.add(curr[0]);
            while (!pq2.isEmpty()) {
                int st = pq2.peek();
                if (st < curr[1] - d) pq2.poll();
                else break;
            }
            ans = Math.max(ans, pq2.size());
        }
        System.out.println(ans);
				br.close();
    }
}