[백준 13334번] 철로

문제 링크: 13334번 제목

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

 

개선의 여지가 꽤 남아있는 코드이다.

list는 각 사람들의 'home' 주소의 목록이다. 그리고 59라인에서도 알 수 있듯, 탐색은 'home' 기준으로 진행한다. 왜 그럴까? rail 길이 내에 들어가는 최대 경로(home-office 경로)의 개수를 구하는 과정을 잘 생각해보면, rail은 반드시 어떤 경로의 'home'에서부터 시작해야 한다. 그렇지 않다면 일부 경로를 포함하지 못하거나, 또는 기껏해야 같은 경로의 수를 포함할 뿐이다.

한편 hq는, 현재 begin부터 rail 길이를 봤을 때, 여기에 포함되는 경로들이다. 60라인은 hq의 경로 중 home이 begin보다 작은 것들을 제외하는 과정이다. for문 끝에서 돌아와 begin이 갱신되었다고 생각할 때, 이들은 제외되어야 하기 때문이다. 64라인은 begin에 대해 end를 저장해주는 과정이다. 참고로 문제를 잘 읽어보면 rail은 엄밀한 의미에서 길이라기보다는... 단순히 office-home을 의미한다.
66라인부터는 oq에서 hq에 해당하는 경로들을 추가해주는 과정이다. 67라인은 당연히 포함되어야 하고, 68라인도 해당 경로에서 office-home과 rail을 비교한 것인데, 전자가 더 크면 결코 rail 길이 내에 포함될 수 없으므로 이를 제외하는 것은 당연한 것이다.

한편 oq는 'office' 주소를 기준으로 정렬되어 있는데, office가 end보다 더 크다면, 해당 경로를 포함해서 그 뒤의 모든 oq의 경로들은 당연히 지금 포함될 수 없는 경로들이다.

이러한 조건, 즉 67, 68, 69라인을 모두 통과했다면 이는 범위에 포함되는 경로이므로 hq에 추가해주고, 이 때 hq의 크기를 계속해서 갱신해주면, 그 중 최댓값이 정답이다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Person {
    int home;
    int office;

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

class HomeComparator implements Comparator<Person> {
    @Override
    public int compare(Person o1, Person o2) {
        if (o1.home != o2.home) return o1.home - o2.home;
        return o1.office - o2.office;
    }
}

class OfficeComparator implements Comparator<Person> {
    @Override
    public int compare(Person o1, Person o2) {
        if (o1.office != o2.office) return o1.office - o2.office;
        return o1.home - o2.home;
    }
}

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

        List<Integer> list = new ArrayList<>();

        PriorityQueue<Person> hq = new PriorityQueue<>(new HomeComparator());
        PriorityQueue<Person> oq = new PriorityQueue<>(new OfficeComparator());

        while (n-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int home = Integer.parseInt(st.nextToken());
            int office = Integer.parseInt(st.nextToken());
            if (home > office) {
                int temp = home;
                home = office;
                office = temp;
            }
            list.add(home);
            oq.offer(new Person(home, office));
        }

        Collections.sort(list);
        int rail = Integer.parseInt(br.readLine());

        int maxSize = 0;
        for (int begin : list) {
            while (!hq.isEmpty() && hq.peek().home < begin) {
                hq.poll();
            }

            int end = begin + rail;

            while (true) {
                if (oq.isEmpty()) break;
                if (oq.peek().office - oq.peek().home > rail) { oq.poll(); continue; }
                if (oq.peek().office > end) break;
                Person p = oq.poll();
                hq.offer(p);
            }

            int size = hq.size();
            if (size > maxSize) maxSize = size;
        }

        System.out.println(maxSize);
    }
}