13334 철로

 

 

1. 풀이

 

다른 블로그를 참고해서 풀었다.

여기에는 스위핑 알고리즘이 사용되는데,

 

스위핑 알고리즘은 특정한 자료구조나 구체적인 코드가 있는 것이 아니라

한 쪽 방향에서 시작해서 다른 방향으로 해결해 나가는 기법이다.

 

문제 풀이를 보면 이해가 갈 것이다.

 

그러면 예제를 가지고 설명하겠다.

 

 

8
5 40
35 25
10 20
10 25
30 50
50 60
30 25
80 100
30

 

 

(5,40) 부터 (80,100) 까지 첫번째 값은 집, 두번째 값은 사무실의 위치를 나타낸다.

하지만 집이 사무실보다 앞에 위치하던지, 뒤에 위치하던지 중요하지 않다.

그저 집과 사무실 거리가 선분 L 보다 작은지가 중요하다.

그러면 집과 사무실이 모두 L 에 포함되기 때문이다.  

 

그래서 리스트에 (5,40) 이런식으로  값을 넣는데, 

(35,25) 처럼 앞에 있는 값이 뒤에 있는 값보다 크면 (25,35) 처럼 더 큰 값이 뒤로 오게 한다.

 

그리고 리스트는 뒤에 있는 값을 기준으로 오름차순 정렬한다.

 

그러면 최종 아래와 같은 순서로 값이 저장된다.

 

10 20

10 25

25 30

25 35

5 40

30 50

50 60

80 100

 

 

그리고 이를 그림으로 나타내면 다음과 같다.

 

 

 

즉, 그림의 맨 아래에 있는 (10,20) 은 리스트의 맨 앞에

맨 위에 있는 (80, 100)은 리스트의 맨 뒤에 있다.

 

그러면 앞 쪽부터 선분 L 이 포함하고 있는지 확인해보자.

 

 

선분 L이 분홍색이다. 예제에서 선분 L은 길이가 30이다.

 

리스트 각 값의 오른쪽 값, 즉 (10,20) 중 20에 맞춰서

선분 L에 포함되는지 확인하고 있다.

(10,20)이 포함되기에 주황색으로 표시했다.

 

 

두번째는 아래와 같다. 

 

 

 

 

 

이렇게 순서대로 진행하다가

선분 L이 최대로 집과 사무실의 위치를 포함하는 경우는 아래와 같이 4구간을 포함할 떄이다.

 

 

 

 

 

 

그리고 아래의 경우처럼 집과 사무실의 거리가 35로, 30을 넘으면 건너뛰면 된다.

 

 

 

 

 

그리고 아래의 경우가 되면, 기존 (10,20), (10,25)가 선분 L에 포함되지 않는다.

 

 

 

 

이를 위해 우선순위 큐를 사용한다.

우선순위 큐는 내림차순 정렬하여, 부모 노드 값이 자식 노드 값보다 작게 한다.

 

그리고 위 과정이 진행될 때마다 리스트의 왼쪽 값을 우선순위 큐에 넣어준다.

즉 맨 처음에 (10,20)에 대해서 선분 L에 포함되는지 확인할 때는

10을 우선순위 큐에 넣어준다.

 

그 다음 (10,25) 에 대해서 선분 L에 포함되는지 확인할 때는

물론 (10,25)의 왼쪽 값, 10도 넣지만,

맨 처음 (10,20)일 때 우선순위 큐에 넣어준 10이 

범위를 벗어나는지 확인한다.

 

즉 현재는 (10,25) 차례로 아래와 같다.

 

 

 

이때 오른쪽 값인 25를 기준으로 선분 L에 포함되는지 확인하기 때문에,

10 < 오른쪽 값 - 선분 L 길이 

이면 (10,20)은 더이상 선분 L에 포함되지 않게 된다.

 

그런데

선분 L의 길이는 30 이므로

25-30 = -5 인데,

10 > -5 이므로

맨 처음의 10은 여전히 선분 L에 포함된다.

 

 

다른 경우로 설명을 하자면,

아래는 우선순위 큐에 10,10,25,25 가 포함되어 있는 상태이고,

오른쪽 값 = 40, 선분 L의 길이는 30이다.

40 - 30 = 10 이며,

10,10,25,25 는 모두 10 이상이기 때문에 선분 L에 포함된다.

 

 

 

 

 

 

하지만 아래의 경우는 

우선순위 큐에 10,10,25,25이 있는데,

오른쪽 값이 50, 선분 L 의 길이가 30이므로

50 - 30 = 20 이고,

10은 20보다 작기 때문에

맨 처음 (10,20) 과 (10,25)와 관련된

2개의 10이 우선순위 큐에서 제거된다.

그리고 선분 L에 포함되는 집과 사무실의 위치도 원래 4였다가 2만큼 줄어들게 된다.

 

 

그리고 (30,50) 차례이므로 우선순위 큐에 30이 들어간다.

 

 

이런식으로 풀면된다.

 

 

2. 최종 코드

 

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


class Position{
	int a;
	int b;
	
	Position(int a, int b) {
		this.a = a;
		this.b = b;
	}
}

public class Main {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = Integer.parseInt(st.nextToken());
	
		ArrayList<Position> input = new ArrayList<>();
		
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int one = Integer.parseInt(st.nextToken());
			int two = Integer.parseInt(st.nextToken());
			
			if(one > two) {
				input.add(new Position(two,one));
			}else {
				input.add(new Position(one,two));
			}
		}
		
	
		Collections.sort(input, new Comparator<Position>() {
			
			@Override
			public int compare(Position p1, Position p2) {
				return p1.b - p2.b;
			}
		});
		
	
		int length = Integer.parseInt(br.readLine());
			
		PriorityQueue<Integer> result = new PriorityQueue<>();
		
		int sum = 0;
		int max = -1;
		
		for(int i=0; i<input.size(); i++) {
			
			int start = input.get(i).a;
			int end = input.get(i).b;
			
			while(!result.isEmpty() && result.peek() < end-length) {
				sum--;
				result.poll();
			}
			
			
			if(start >= end-length) {
				sum++;
				result.add(start);
			}
			
			max = Math.max(max, sum);
		}
		
		System.out.println(max);
	}
}

 

 

참고 자료 : 

 

https://byeo.tistory.com/entry/%EC%8A%A4%EC%9C%84%ED%95%91-Sweeping

스위핑 (Sweeping)

 

https://blog.naver.com/occidere/221085858307

[백준] 13334 - 철로

 

https://for-development.tistory.com/120

백준 13334 철로(JAVA)