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);
}
}