[BaekJoon] 13334 철로 (Java)

1.  문제 링크

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

2.  문제

요약

• 집과 사무실을 통근하는 n명의 사람들이 있는데 각 사람의 집과 사무실은 수평선 상에 있는 서로 다른 점에 위치합니다.
• 임의의 두 사람 A, B에 대하여, A의 집 혹은 사무실의 위치가 B의 집 혹은 사무실의 위치와 같을 수 있습니다.
• 통근을 하는 사람들의 편의를 위해 일직선 상의 어떤 두 점을 잇는 철로를 건설하여, 기차를 운행하려고 하는데, 제한된 예산으로 인해 철로의 길이는 d로 정해져 있습니다.
• 집과 사무실의 위치 모두 철로 선분에 포함되는 사람들의 수가 최대가 되도록 철로 선분을 정하려고 합니다.
• 철로의 길이를 나타내는 양의 정수 d와 통근하는 사람들의 집과 사무실의 위치를 나타내는 정수쌍 ($h_i, o_i$)가 n개 주어질 때, 집과 사무실의 위치가 모두 선분 L에 포함되는 사람들의 최대 수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 100,000보다 작거나 같은 양의 정수인 사람 수를 나타내는 n이 주어지고 두 번째 줄부터 n개의 줄에 정수 쌍 ($h_i, o_i$)가 주어집니다. $h_i$와 $o_i$는 각각 사람 i의 집과 사무실의 위치를 나타내고 -100,000,000 이상 100,000,000 이하의 서로 다른 정수입니다. 마지막 줄에 1보다 크거나 같고 200,000,000보다 작거나 같은 정수인 철로의 길이를 나타내는 d가 주어집니다.
• 출력: 첫 번째 줄에 길이 d의 임의의 선분에 대하여, 집과 사무실 위치가 모두 그 선분에 포함되는 사람들의 최대 수를 출력합니다.

3.  소스코드

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

public class Main {
    static int n, d;
    static PriorityQueue<Route> routes;

    static void input() {
        Reader scanner = new Reader();

        n = scanner.nextInt();
        routes = new PriorityQueue<>();

        for(int route = 1; route <= n; route++) {
            int loc1 = scanner.nextInt(), loc2 = scanner.nextInt();
            routes.offer(new Route(Math.min(loc1, loc2), Math.max(loc1, loc2)));
        }

        d = scanner.nextInt();
    }

    static void solution() {
        PriorityQueue<Integer> locations = new PriorityQueue<>();

        int count = 0, answer = 0;
        while(!routes.isEmpty()) {
            Route route = routes.poll();

            while(!locations.isEmpty() && locations.peek() < (route.end - d)) {
                locations.poll();
                count--;
            }

            if(route.start >= (route.end - d)) {
                locations.offer(route.start);
                count++;
            }

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

        System.out.println(answer);
    }

    static class Route implements Comparable<Route> {
        int start, end;

        public Route(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public int compareTo(Route r) {
            if(this.end != r.end) return this.end - r.end;
            return this.start - r.start;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 통근을 하는 사람의 집과 사무실 위치를 나타내기 위해 Route 클래스를 정의합니다.
  • 집과 사무실 중 더 앞서는 번호를 담는 start 변수와 더 나중 번호를 담는 end 변수를 멤버 필드로 갖습니다.
  • PriorityQueue에 넣어 정렬을 할 예정이므로 Comparable 인터페이스를 구현하여 정렬 기준을 설정합니다.
    • end 기준 오름차순으로, end 값이 같다면 start 기준 오름차순으로 정렬합니다.

• 주어진 통근하는 사람들의 정보를 Route 객체로 만들어 routes라는 PriorityQueue에 담습니다.
• Route의 start 값들을 담을 locations라는 PriorityQueue를 생성합니다.
• 선택된 정보의 개수를 나타내는 변수 count와 그 중 최댓값을 저장할 변수 answer를 생성하고 0으로 초기화합니다.
• routes에 있는 객체들을 순회하면서 포함되는 사람들의 최대 수를 구합니다.
  • routes에서 Route 객체를 하나 뽑아 route라는 변수에 저장합니다.
  • locations가 비어있지 않고 locations에서 가장 작은 수가 (route의 end 값 - d)보다 작을 때까지 locations에서 값을 하나씩 빼고 count 값을 1 감소시킵니다.
    • locations 내에 들어있는 값들은 선택된 정보들을 나타냅니다.
    • 시작 지점의 값을 넣어놓고 새로운 Route 객체들이 나올 때마다 해당 Route 객체의 end 값을 철로의 마지막 지점이라고 가정합니다.
    • 철로의 마지막 지점이 변경되었기 때문에 길이 d 안에 포함되지 않는 값들이 locations 내에 포함될 수 있습니다.
    • 그렇기 때문에 route의 end 값부터 d 길이의 철로 내에 포함되지 않는 값들을 제거하기 위해 위 작업을 진행합니다.
    • locations에서 값이 빠졌다는 것은 선택된 정보가 빠져나갔다는 뜻이므로 count의 개수 또한 줄어듭니다.
  • 그 후에 route의 start 값이 (route의 end 값 - d)보다 크거나 같은지 확인하고 만약 그렇다면 locations에 route의 start 값을 넣고 count를 1 증가시킵니다.
    • start 값이 (end 값 - d)보다 작다면 d라는 길이 내에 집과 직장이 모두 포함되지 않으므로 이를 확인합니다.
  • count 값과 answer 값을 비교하여 더 큰 값으로 answer 값을 갱신시킵니다.