22867 종점

 

 

1. 풀이

 

 

1) 입력값 변환

 

예제에 보면

입력값이 

 

06:00:00.000 06:30:00.000

 

이런식으로 되어 있다.

이 값들을 String으로 받은 뒤,

 

: 와 .를 공백으로 바꿔준다.

 

이때 replaceAll 메서드를 사용한다.

06:00:00.000 

이 값이 String a 라고 하면,

 

		a= a.replaceAll("[.:]", "");

이런식으로 바꿔주면 된다.

 

1) 

앞부분 =>  "[.:]" 

정규표현식을 사용한 것이다.

즉 문자 "." 또는 ":" 를 의미한다.

 

2) 

뒷부분 => ""

즉 공백을 의미한다.

 

3) 

결론 => 

문자 "." 또는 ":" 를 공백으로 바꾸라는 의미이다.

 

 

 

 

그러면

 

06:00:00.000 

이 값은 

replaceAll 메서드 적용 뒤

 

060000000 

이렇게 된다.

 

그 후 이 값을 int 형으로 바꿔준다.

그러면  

60000000 

이렇게 된다.

 

이런 식으로 입력값들을 바꿔주면 된다.

 

 

2) 리스트에 입력값 넣기

 

예제에 나온 값들을 위와 같이 변환해 준 뒤,

리스트에 

(버스가 종점에 들어오는 시각, 나가는 시각) 을 쌍으로 넣어준다.

 

그런 다음 리스트를

들어오는 시각 기준 오름차순 정렬,

나가는 시각 기준 오름차순 정렬해준다.

 

그러면 아래의 예제 입력값은

 

06:00:00.000 06:30:00.000
06:10:45.000 06:15:00.000
06:30:00.000 06:40:00.000
06:01:00.001 06:40:00.001

 

아래와 같이 변해서 리스트에 정렬되어 있는 상태이다.

 

 

60000000  63000000
60100001  64000001
61045000  61500000
63000000  64000000

 

3) 우선순위 큐 사용

 

 

그러면 이제 우선순위 큐를 사용해보자.

우선순위 큐는 오름차순 정렬이다.

 

우선순위 큐에는 

버스가 종점에서 나가는 시각만 넣을 것이다.

 

1. 첫 번째

 

우선순위 큐에 아무 값도 없으므로 첫 번째 버스의 종점에서 나가는 시각, 

즉 63000000 값을 우선순위 큐에 넣는다.

 

 

2.  두 번째

 

두 번째 버스의 도착 시간(60100001) 과

우선순위 큐의 맨 위에 있는 값, 즉 첫번째 버스의 종점에서 나가는 시각(63000000) 을 비교한다.

 

예를 들어

첫 번째 버스의 나가는 시각 <= 두 번째 버스의 도착 시각

이면, 

첫 번째 버스가 종점에서 나간 다음에

두 번째 버스가 들어오기 때문에, 

첫 번째 버스는 나간 상태이다.

그래서 첫 번째 버스의 종점에서 나가는 시각을 우선순위 큐에서 제거해준다.

그리고 두 번째 버스의 종점에서 나가는 시각을 우선순위 큐에 넣어준다.

 

즉, 우선순위 큐를 통해 동시에 종점에 있는 버스들을 알 수 있다.

 

하지만 이 경우는 

첫번째 버스의 나가는 시각 > 두번째 버스의 도착 시각

이므로, 그냥 두번째 버스의 종점에서 나가는 시각(64000001) 을 우선순위 큐에 넣어주면 된다.

 

그리고 우선순위 큐 사이즈 중

가장 큰 값을 정답으로 출력하면 된다.

 

 

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 Time{
	int one;
	int two;
	
	Time(int one, int two) {
		this.one = one;
		this.two = two;
	}
}


public class Main {

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

		ArrayList<Time> input = new ArrayList<>();
		
		for(int i=0; i<N; i++ ) {
			
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			
			String a = st.nextToken();
			String b = st.nextToken();
			a= a.replaceAll("[.:]", "");
			b= b.replaceAll("[.:]", "");
	
			input.add(new Time(Integer.parseInt(a),Integer.parseInt(b)));
		}
		
	
		
		Collections.sort(input, new Comparator<Time>() {
			@Override
			public int compare(Time t1, Time t2) {
				if(t1.one == t2.one) {
					return t1.two - t2.two;
				}else {
					return t1.one - t2.one;
				}
			}
		});
		

		PriorityQueue<Integer> result  = new PriorityQueue<>();
	
		int max = -1;
		for(int i=0; i<input.size(); i++) {
			
			int value1 = input.get(i).one;
			int value2 = input.get(i).two;
			
			while(!result.isEmpty() && result.peek()<= value1) {
				
				result.poll();
				
			}
		
			result.add(value2);
			max = Math.max(max, result.size());
			
		}
		
		System.out.println(max);
	}
}