[백준] 13334: 철로 - JAVA

22 Aug 2023 in Algorithm on 자료 구조

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

풀이

n명의 사람에 대해 2개씩 점의 위치가 주어지고,

d길이의 선을 위치했을 때 2개의 점이 모두 선 안에 있는 사람의 최댓값을 구하는 문제이다.

입력을 받으면서 우선순위큐에 저장했다.

우선순위큐의 정렬 조건은 오른쪽 점을 오름차순으로, 오른쪽 점이 같을 경우 왼쪽 점을 오름차순으로 했다.

또 다른 우선순위큐을 만들어 개수를 세는 용도로 사용했다.

첫번째 우선순위큐를 pq라 하고, 두번째 우선순위큐를 count라고 했다.

pq에서 값을 빼서 count에 넣는다.

이때 선분 d의 오른쪽 점을 pq에서 뺀 값의 오른쪽 점으로 하고,

이 선분에 왼쪽 점이 속해있지 않는 값들을 count에서 뺀다.

그 후 최댓값을 count의 size와 비교하여 갱신한다.

---

메모리: 46684KB

시간: 784ms

언어: Java 11

코드

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

public class Main {
    static class Node implements Comparable<Node> {
        int left;
        int right;

        public Node(int left, int right) {
            this.left = left;
            this.right = right;
        }

        @Override
        public int compareTo(Node o) {
            if (this.right == o.right) {
                return Integer.compare(this.left, o.left);
            }
            return Integer.compare(this.right, o.right);
        }
    }

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

        PriorityQueue<Node> pq = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            pq.add(new Node(Math.min(a, b), Math.max(a, b)));
        }

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

        int max = 0;
        PriorityQueue<Integer> count = new PriorityQueue<>();
        while (!pq.isEmpty()) {
            Node curr = pq.poll();
            count.add(curr.left);

            while (!count.isEmpty() && curr.right - d > count.peek()) {
                count.poll();
            }

            max = Math.max(max, count.size());
        }

        System.out.println(max);
    }

}