문제
한 개의 회의실이 있는데 이를 사용하고자 하는 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) 를 이용할 수 있다.
리뷰
어떻게 풀어야 할지 방법은 떠올랐다.
회의 시작 시간을 기준으로 정렬을 하는게 아니라
회의가 끝나는 시간을 기준으로 먼저 정렬을 하면 최대한 많은 회의를 진행할 수 있다.
근데 문제는 회의 시작 시간과 끝나는 시간을 함께 저장하여 정렬을 하는 방법을 몰랐다.(쉣)
맵으로 하자니 key값이 중복이 안되고 list를 활용하자니 시작 값과 종료 값이 필요해 담을 수 없었다.
이건 문법적인 문제라 생각하여 인터넷의 힘을 빌렸다ㅜㅜ 공부 더 열심히 하자!
public class Q1931 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int max = sc.nextInt();
int[][] arr = new int[max][2];
for(int i=0; i< arr.length; i++){
arr[i][0] = sc.nextInt();
arr[i][1] = sc.nextInt();
}
sc.close();
Arrays.sort(arr,(a,b) ->{
if (a[1] == b[1]){
return a[0] - b[0];
}
return a[1] - b[1];
});
int end = 0;
int cnt = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i][0] >= end){
cnt++;
end = arr[i][1];
}
}
System.out.println(cnt);
}
}코드 리뷰
- 먼저 최대 회의 개수를 입력 받는다
- 최대 회의 개수만큼의 2차원 배열을 선언하여 각 요소에 시작 값과 종료 값을 받는다.
- Arrays.sort를 이용해 각 배열의 값들을 비교하고 정렬을 한다
내가 이 부분을 몰랐다
이 때, sort의 첫 인자 값으로는 비교를 할 배열 arr을 넣어줬고, 2번째 인자 값으로 람다를 이용하여 Comparator의 compare 함수를 구현하여 arr에 들어있는 각 배열을 넘겨줬다.- 만약 종료하는 시간(a[1], b[1])이 같다면,
시작하는 시간(a[0], b[0])을 기준으로 비교를 하여,
a[0] - b[0]이 양수라면 a[0]이 더 크다는 얘기이므로 오름차순 정렬을 위해 둘의 위치를 바꾸고, 음수가 나오면 위치를 바꾸지 않고 그대로 둔다.- 종료 시간이 서로 다르다면,
4에서 했던 것과 마찬가지로
a[1] - b[1]이 양수라면 a[1]이 더 크다는 얘기이므로 오름차순 정렬을 위해 둘의 위치를 바꾸고, 음수가 나오면 위치를 바꾸지 않고 그대로 둔다.- 이제 정렬은 끝났으니 끝나는 시점을 저장할 변수 end와 회의의 개수를 저장할 cnt를 선언한다.
- 반복문을 통해 저번 회의가 끝난 시점(end)이 현재 회의가 시작하는 시점(arr[i][0])보다 작거나 같다면 회의 개수(cnt)를 1 증가시키고, 회의 종료 시점(end)를 현재 회의가 끝나는 시점(arr[i][1])으로 변경한다.
