[백준] 13334번 : 철도

철도

---

풀이 방법

우선 좌표가 (-100,000,000 ~ 100,000,000) 이기 때문에 그냥 무작정 찾아버리면 시간초과에 걸리기 마련이다.

그래서 시간복잡도가 $O(logN)$ 인 우선순위 큐를 사용해서 탐색을 진행한다.

내 구현을 크게 표현하면
1. 시작을 집, 끝을 사무실로 두고 끝 점을 기준으로 오름차순 정렬해 PriorityQueue에 저장
2. PriorityQueue에서 하나씩 꺼내서, 집과 사무실과의 거리가 주어진 거리 $d$ 보다 작거나 같으면 새로운 PriorityQueue에 저장.
3. 새로운 PriorityQueue 는 시작 점 기준으로 오름차순 정렬해 PriorityQueue의 끝 점과 거리를 계산해 주어진 거리 $d$ 보다 작으면 큐에 유지, $d$ 범위에 없다면 큐에서 제거한다.

느낀 점

막상 구현해보면 간단한데, 처음에는 정렬을 잘못해서 시작점 기준으로 정렬하고 시작점을 비교하는 어이없는 실수를 저질렀다..

새로 알게된 점은 Comparator.comparingInt와 람다 함수를 이용하면 보다 짧은 코드로 클래스 내의 원하는 필드를 기준으로 정렬이 가능하다는 점을 알았다.

이런 비슷한 문제를 봤었는데, 스위핑이라는 알고리즘에 대해선 좀 더 많은 문제를 풀어봐야 익숙해질 것 같다..

다음 블로그를 통해 해당 문제의 구조를 정확히 이해했는데, 설명이 이해되지 않았다면 이 블로그를 참고하자

참고 블로그 : https://chanhuiseok.github.io/posts/baek-28/

---

소스 코드

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

class Person{
    int home;
    int office;
    public Person(int home, int office) {
        this.home = home;
        this.office = office;
    }
}

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        PriorityQueue<Person> heap = new PriorityQueue<>(Comparator.comparingInt(o -> o.office));

        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            int h = Integer.parseInt(st.nextToken());
            int o = Integer.parseInt(st.nextToken());
            heap.add(new Person(Math.min(h,o),Math.max(h,o)));
        }

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

        PriorityQueue<Person> temp = new PriorityQueue<>(Comparator.comparingInt(o -> o.home));
        while(!heap.isEmpty()){
            Person p = heap.remove();
            int start = p.home;
            int end = p.office;

            if(end-start <= d){
                temp.add(p);
            }

            while(!temp.isEmpty()){
                Person p2 = temp.peek();
                if(end - p2.home > d){
                    temp.remove();
                } else {
                    break;
                }
            }
            count = Math.max(count,temp.size());
        }

        System.out.println(count);

    }
}