[PS] BOJ13334 철로 ( Line Sweeping ) with JAVA

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

13334번: 철로

 

 

◎ 문제풀이 

 

[백준] 13334 - 철로

 

위 포스팅을 참고하여 풀었다. 

 

아무리 생각해도 시간복잡도가 O(N²) 풀이만 생각났는데 최소Heap을 이용하면 O(NlogN) 시간복잡도가 가능했다. 

 

1) Line들을 Line 테이블에 저장하고 끝점을 기준으로 오름차순 정렬한다.

2) 오름차순으로 정렬된 Line 테이블에서 Line 하나를 가져와 시작점을 PriorityQueue(최소Heap)에 넣는다.

3) 이렇게 하면 하나의 범위가 형성된다. 

 

PriorityQueue에 들어간 시작점은 현재까지 시작점 중 최솟값이다. 

오름차순으로 정렬된 Line테이블에서 가져온 Line의 끝점은 현재까지 끝점 중 최댓값이다.

 

현재까지 최대인 끝점을 철로의 끝점으로 한다면

( 끝점 - d )가 철로의 시작점이 된다. 

 

만약 PriorityQueue의 peek 지점이 철로의 시작점보다 작으면 PriorityQueue에서 제거한다. 

위 조건대로 제거를 반복하면

PriorityQueue에는 철로의 시작점보다 같거나 큰 시작점만이 남는다.

 

그러므로

PriorityQueue에 남아있는 시작점의 개수가 곧 철로 범위에 포함되는 Line의 수이다. 

 

4) N개의 Line을 오름차순으로 가져오면 N개의 철로가 생성되고 N개의 철로에 포함된 Line의 수는 PriorityQueue의 size로 결정된다. 매반복마다 size의 최댓값을 구하면 된다. 

 

◎ 코드

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

//BOJ13334 철로
public class Main {

    public static class Line implements Comparable<Line>{
        int start;
        int end;
        int length;

        public Line(int start, int end){
            this.start = start;
            this.end = end;
            this.length = end - start;
        }

        @Override
        public int compareTo(Line l) {
            return this.end - l.end;
        }
    }

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

        int n = Integer.parseInt(br.readLine());
        Line[] lines = new Line[n];

        StringTokenizer st;

        for(int i=0;i<n;i++){

            st = new StringTokenizer(br.readLine());

            int h = Integer.parseInt(st.nextToken());
            int o  = Integer.parseInt(st.nextToken());
            
            // 집과 오피스의 위치 중 작은 값을 시작점으로 하기
            if(h<o) lines[i] = new Line(h,o);
            else lines[i] = new Line(o,h);

        }
        
        // 철로의 길이
        int d = Integer.parseInt(br.readLine());
        
        // 끝점을 기준으로 오름차순 정렬
        Arrays.sort(lines);

        // 우선순위 큐
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int ans = 0;

        for(int i=0;i<n;i++){
            // 오름차순대로 Line 하나 가져오기 
            pq.add(lines[i].start); // Line의 시작점을 PriorityQueue에 넣기 
            
            // 철로의 시작점보다 시작점이 앞에 있는 Line 쳐내기
            while(!pq.isEmpty() && pq.peek() < lines[i].end - d) pq.remove();
            
            // PriorityQueue에 남아있는 Line은 철로에 포함되는 Line
            // 최댓값 갱신하기
            ans = Math.max(ans,pq.size());
        }

        // 출력
        System.out.println(ans);


    }
}