출처 : https://www.acmicpc.net/problem/1931
회의실배정 분류
문제
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
입력
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.
예제 입력 1
11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14
예제 출력 1
4
힌트
(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.
1931 백준 회의실배정 자바 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
public class MeetingRoom_dh {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int num = Integer.parseInt(st.nextToken());
int arr[][] = new int[num][2];
for(int i=0; i<num; i++) {
st = new StringTokenizer(br.readLine());//하나의 행을 읽어옵니다.
for(int j=0;j<2;j++) {
arr[i][j]=Integer.parseInt(st.nextToken()); //해당 행에서 존재하는 값을 추출하여 배열에 넣습니다.
}
}
//정렬을 하여 비교를 원활하게 하기위함 입니다.
Arrays.sort(arr, new Comparator<int[]>() {
@Override
public int compare(int[] start, int[] end) {
if(start[1]==end[1]){
//만약 비교하는 값의 종료시간이 같을 경우 시작시간으로 정렬합니다.
return Integer.compare(start[0], end[0]);
}
//종료시간에 따라 정렬합니다.
return Integer.compare(start[1], end[1]);
}
});
int cnt = 0;
int end = -1; //비교하기 위한 값
for(int k=0; k<num;k++) {
//각행의 1열과 0열을 비교하기 위해서 입니다.
//비교하여 같거나 큰값을 다시 비교할 값에 넣습니다.
if(arr[k][0]>=end) {
end = arr[k][1];
cnt++;
}
}
System.out.println(cnt);
}
}
문제 분석
회의실배정 를 분석해보면 다음과 같은 규칙이 있습니다.
1. 각 배열의 1열과 0열을 비교합니다.
2. 최댓값을 구하기 위해서 배열을 사용하여 정렬을 합니다.
Comparator
이번 문제로 정렬에 대해 자세히 배우게 된 것 같습니다.
원래 Comparator 정렬에 대해서 있다는 것은 알고 있었지만 정확한 사용법은 알지 못했습니다.
Comparator를 이용한 정렬에 대해서 잠시 설명하자면 Comparator를 이용하면 정렬 기준을 본인이 원하는 대로 바꾸는 것이 가능합니다. 오름차순은 매개 순서를 그대로 하면 되고 내림차순은 매개순서를 바꿔주면 됩니다.
ex) return Integer.compare(start[0], end[0]); //오름차순
return Integer.compare(end[0], start[0]); //내림차순
(위의 예시 활용)
Comparator에 대한 자세한 사용법은 링크를 남깁니다.
https://m.blog.naver.com/occidere/220918234464
https://ifuwanna.tistory.com/232
includestdio.tistory.com/35includestdio.tistory.com/35
감사합니다
댓글