[백준] 13334- 철로 문제 풀이(자바,Java)

문제

13334번: 철로

들어가며

이 문제는 선형 탐색으로 풀면 O(N^2)으로 시간 초과가 발생한다.

그렇기에 다른 방식을 탐색해야 하는데 우선순위 큐를 사용해서 풀 수 있다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;

public class 철로_13334_3 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        ArrayList<Road> roads = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int[] s = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt)
                    .toArray();
            roads.add(new Road(Math.min(s[0], s[1]), Math.max(s[0], s[1])));
        }
        Collections.sort(roads);
        int d = Integer.parseInt(br.readLine());
        PriorityQueue<Double> pq = new PriorityQueue<>();
        int result = 0;

        for (var pos : roads) {
            double start = pos.start;
            double end = pos.end;

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

            // 현재 선로의 시작점을 큐에 추가
            if (start >= end - d){
                pq.add(start);
            }

            // 큐의 크기가 현재 범위 내 포함된 선로의 개수
            result = Math.max(result, pq.size());
        }
        System.out.println(result);
    }

    private static class Road implements Comparable<Road> {
        double start;
        double end;

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

        @Override
        public int compareTo(Road o) {
            int compare = Double.compare(end, o.end);
            if (compare == 0) {
                return Double.compare(start, o.start);
            }
            return compare;
        }
    }
}

풀이

크게 두 방식이 있다.

하나는 시작점을 기준으로 정렬하는 것과 끝점으로 정렬하는 방법이 있다.

크게 다르진 않다.

이 글에선 끝점으로 정렬하는 경우를 다룬다.

 

정렬에 대해서도 잘 생각해야 한다.

private static class Road implements Comparable<Road> {
    double start;
    double end;

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

    @Override
    public int compareTo(Road o) {
        int compare = Double.compare(end, o.end);
        if (compare == 0) {
            return Double.compare(start, o.start);
        }
        return compare;
    }
}

끝점이 작은 것부터 앞으로 정렬을 하되 시작점 또한 오름차순으로 정렬한다.

for (int i = 0; i < n; i++) {
    int[] s = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt)
            .toArray();
    roads.add(new Road(Math.min(s[0], s[1]), Math.max(s[0], s[1])));
}

이때, 문제에선 집보다 오피스 좌표가 앞에 있는 경우의 수가 있으므로 하나로 통일해준다. 이 글에선 집을 start로 보기 때문에, 집을 앞에 와도록 좌표 값을 교환해 준다.

(집과 오피스는 결국 시작과 끝점 역할이지 둘이 서로 바껴도 전혀 문제에 지장이 없다)

 

Collections.sort(roads);
int d = Integer.parseInt(br.readLine());
PriorityQueue<Double> pq = new PriorityQueue<>();
int result = 0;

for (var pos : roads) {
    double start = pos.start;
    double end = pos.end;

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

    // 현재 선로의 시작점을 큐에 추가
    if (start >= end - d){
        pq.add(start);
    }

    // 큐의 크기가 현재 범위 내 포함된 선로의 개수
    result = Math.max(result, pq.size());
}
System.out.println(result);

정렬을 하고 이제부터 우선 순위 큐를 이용한다.

이때, 먼저 도로를 기준으로 반복문을 돈다.

 

이는 철로를 놓을 기준을 잡기 위한 것으로, 철로 길이에 맞춰 철로의 길이가 만들어진다.

끝점을 기준으로 철로를 놓는다. 그게 end - d이다. 

우선순위 큐엔 현재 끝점에서 선로를 놓았을 때, 닿는 집의 출발점들만 넣어둔다.

그렇기에 end - d 보다 출발점이 작다면, 그건 철로가 닿지 않는 곳이므로 전부 poll을 해준다.

if (start >= end - d){
    pq.add(start);
}

그 이후, 현재 선로을 넣을 수 있는지 파악한다.

 

result = Math.max(result, pq.size());

마지막으로 현재 선로의 개수를 세서 이전 값들과 비교한다.

우선 순위 큐엔 놓을 수 있는 선로들만 넣기로 했으므로 size가 곧 개수이다.