[BOJ] 백준 10165번 버스 노선 (Java)

#10165 버스 노선

난이도 : 플레 5

유형 : 그리디 / 정렬

10165번: 버스 노선

▸ 문제

국경을 따라 순환 도로를 건설한 국가가 있다. 이 순환 도로에는 N개의 위치에 버스 정류소가 있으며, 버스 정류소에는 0부터 N-1까지 번호가 시계방향 순서로 지정되어 있다. 현재 여러 개의 버스 노선들이 이 순환 도로에서 운행되고 있다. 각 버스 노선은 [a, b]로 표시된다. 이 노선의 버스는 버스 정류소 a부터 b까지를 시계방향으로, b부터 a까지는 반시계방향으로 운행한다. 순환 도로 상의 모든 정류소를 포함하는 버스 노선은 존재하지 않는다.

국가 교통행정부에서 비용 절감을 위해서 버스 노선 중 일부를 취소하려고 한다. 취소되는 노선은 다른 노선에 포함되어 있는 노선이다. 예를 들어, N=10일 때, 5개의 버스 노선이 다음과 같이 있다고 하자. 

[0, 4], [2, 6], [5, 0], [7, 9], [9, 4]

위 그림에서 버스 노선 ①은 ⑤에 포함되고, 버스 노선 ④는 ③에 포함된다. 버스 노선 ②, ③, ⑤를 포함하는 노선은 없다. 따라서 취소되는 버스 노선은 ①과 ④이다.

버스 노선에 대한 정보가 주어질 때, 취소되지 않고 계속 운행되는 버스 노선을 모두 출력하는 프로그램을 작성하시오. 

▸ 입력

첫 번째 줄에는 버스 정류소의 개수 N(3 ≤ N ≤ 1,000,000,000)이 주어지고 두 번째 줄에는 버스 노선의 수 M(2 ≤ M ≤ 500,000)이 주어진다. 각 버스 노선은 1부터 M까지의 번호로 구분된다. 그 다음 M개의 줄에는 1번 노선부터 순서대로 각 버스 노선 [a, b]를 나타내는 두 개의 정수 a와 b가 한 줄에 주어진다, 단, 0 ≤ a, b ≤ N-1이고 a ≠ b이며 동일한 버스 노선이 두 번 이상 입력으로 주어지는 경우는 없다. 또한 순환 도로 상의 모든 정류소를 포함하는 버스 노선은 존재하지 않는다.

▸ 출력

입력으로 주어진 버스 노선들 중에서 다른 노선에 포함되지 않은 노선들의 번호를 번호가 작은 것부터 순서대로 빈칸을 사이에 두고 출력한다.

 

문제 풀이  

주어지는 버스 노선 중 이미 다른 노선과 겹치는 노선을 제외해주는 문제이다.

 

📚 조건

• 버스 정류소 개수 N ( 3 <= N <= 1,000,000,000)
• 버스 노선의 수 M ( 2 <= M <= 500,000)
• 버스 노선 [a,b] ( 0 <= a,b <= N-1 ), a != b

구상

1. 버스 노선의 정보를 입력받는다.
   1. 만약 시작 정류장이 도착 정류장보다 더 클 경우 해당 노선은 시작점 한 번 지난 노선이기 때문에 도착 정류장 +n을 해준다.  route.s > route.e (3,5번 노선)
   2. 1-1)에 해당하는 (도착 정류장+n)의 가장 큰 값(last)을 저장해놓는다.
2. 해당 노선의 정보를 시작 정류장을 기준으로 오름차순 정렬해준다.
   1. 만약 시작 정류장이 같을 경우 도착 정류장이 큰 순서대로 내림차순을 해준다.
3. 첫 번째 거르기 : 양방향 Queue인 Deque를 이용하여 이전 노선의 도착 정류장보다 해당 노선의 도착 정류장이 작을 경우 삭제한다.  (노선의 정보는 시작 정류장을 기준으로 오름차순이기 때문)
4. 두 번째 거르기 : 1-2)에 저장해놓은 데이터보다 작은 시작 정류장의 노선이 있다면 해당 노선은 삭제한다.

 

스케치

1번 로직

해당 노선들은 다음과 같이 저장된다.

(노선 번호, 시작 정류장, 도착 정류장) = (1,0,4), (2,2,6), (3,5,10), (4,7,9), (5,9,14)

버스 노선

→ 여기서 가장 시작점을 한 번 지나고 도착하는 마지막 정류장(last)은 14 (5번 노선)이다.

2~3번 로직

정렬을 해주는 이유는 그리디 알고리즘 최적의 해를 찾아내기 위함이다.

 

1) 시작 정류장을 기준으로 정렬된 데이터는 도착 정류장만 비교해도 된다. 이전 노선보다 도착 정류장이 작으면 해당 노선은 제외한다. ( i+e < i+1.e )

 

2) 시작 정류장이 같을 경우 마지막 정류장을 내림차순으로 정렬한 이유도 마찬가지이다.  ( i번 노선.s == i+1번 노선.s , i+e < i+1.e )

 

4번 로직

마지막으로 도착 정류장이 시작점을 넘어선 경우를 고려해주면 된다. (1번노선, 5번노선)

 

두 가지 전제 조건

1. 시작점을 지나는 정류장 중 마지막으로 도착하는 정류장은 4번이다. (1번로직)
2. 정렬된 데이터이므로 i번 노선보다 i+1번의 노선 시작 정류장의 숫자가 더 크다. (i+1.s > i.s)

마지막 도착하는 정류장은 여러 로직을 거쳐 정렬된 데이터에 마지막 부분에 저장되어 있을 것이다.  그러므로 만약 앞에 있는 데이터가 마지막 데이터보다 도착 정류장이 작다면 아래와 같이 포함되어 있는 것이므로 삭제해준다. (i.e <= last)

 

마지막으로 그런 다음 남은 노선 번호들을 오름차순으로 정렬해서 출력해주면 된다.

 

풀이 코드 

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st =  null;
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		
		int last =0;
		List<Route> list = new ArrayList<>();
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			
			if(s>e) { // 시작점 통과하는 노선
				last = Math.max(last, e); // 가장 나중에 도착하는 정류장 번호
				e += n; // 도착 정류장+n
			}
			list.add(new Route(i+1, s,e));
		}
		
		Deque<Route> q= new ArrayDeque<>();
		Collections.sort(list); // 시작 정류장 오름차순 정렬 (시작 정류장 같으면 도착 정류장 내림차순)
		for(Route r : list){
			// 첫 번째 거르기
			// 이전 노선의 도착 정류장보다 해당 노선의 도착 정류장이 큰 경우에만 저장
			// (i.e < i+1.e)
			if(q.isEmpty() || q.getLast().e < r.e ) {
				q.add(r); 
			}
		}
		// 두 번째 거르기
		// 시작점을 지나는 노선의 도착 정류장보다 작은 노선들 제거 (i.e <= last)
		while (!q.isEmpty() && q.getFirst().e <= last) {
			Route r = q.removeFirst();
		}
		
		List<Integer> res = new ArrayList<>();
		while (!q.isEmpty()) {
			int idx = q.poll().idx;
			res.add(idx);
		}
		Collections.sort(res, (a,b) -> (a-b));
		for(int idx : res) {
			System.out.print(idx+" ");
		}
	}
}

class Route implements Comparable<Route>{
	int idx;
	int s;
	int e;
	
	public Route(int idx, int s, int e) {
		this.idx = idx;
		this.s = s;
		this.e = e;
	}

	@Override
	public int compareTo(Route o) {
		if(this.s == o.s) {
			return o.e - this.e; // 시작이 같을 경우, 도착 노선 큰 순서대로 내림차순
		}
		return this.s - o.s; // 시작 노선 오름차순 
	}
}