[014] 1931.회의실 배정
https://www.acmicpc.net/problem/1931
1931번: 회의실 배정
(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.
www.acmicpc.net
진짜 머리 빠개지는 줄 알았음 타임오버 개새끼
회의실 사용은 시작시간 / 끝나는 시간이 주어진 상태고, 여기에서 최대로 많은 회의를 진행해야 한다.
그렇다면 여기서 중요한 포인트는
시작시간-끝나는 시간이 작은 것이다. 당연함. 회의 시간이 짧을수록 많은 팀을 우겨넣을 수 있다.
그렇다면 정렬을 할 때
1. 끝나는 시간을 기준으로
2. 끝나는 시간이 같다면 회의 시간이 적은 것으로
구현을 하면 되시겠다
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] arr = new int[n][2];
int count = 0;
int end = 0;
for(int i = 0; i < n; i++){
arr[i][0] = sc.nextInt();
arr[i][1] = sc.nextInt();
}
Arrays.sort(arr, (int[] fst, int[] snd) -> {
if(fst[1] == snd[1]){
return fst[0] - snd[0];
}else{
return fst[1] - snd[1];
}
});
do{
int temp = 0;
for(int i = 0 ; i < n; i ++){
if(arr[i][0] >= end){
end = arr[i][1];
count ++;
break;
}
}
}while(end != arr[n-1][1]);
System.out.println(count);
}
}
처음 결과
는 당연히 시간 초과가 떴다. 뻘짓을 391418291232189319나번 정도 하고 나서...
생각해보니 do while이 왜 저기있는지 모르겠다. 아마 풀면서 지우는 걸 까먹은 거 같음 ^^!
그것도 모르고 이리 바꾸고 저리 바꾸고 sort를 지우고 처음 입력받을 때마다 정렬을 수행했다가 아주 별짓을 다했다...
다 제대로 풀어놓고 마지막에 정신 놓은 수준 (...!)
그리고 나서 제출
저 while 깨닫는 거 30분 걸렸다(^^)!
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] arr = new int[n][2];
int count = 0;
int end = 0;
int temp = 0;
for(int i = 0; i < n; i++) {
arr[i][0] = sc.nextInt();
arr[i][1] = sc.nextInt();
}
Arrays.sort(arr, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if(o1[1] == o2[1]) {
return o1[0] - o2[0];
}
return o1[1] - o2[1];
}
});
for(int i = 0; i < n; i ++){
if(end <= arr[i][0]){
end = arr[i][1];
count++;
}
}
System.out.println(count);
}
}
나는 Comparator를 사용하는 것보다 람다식을 사용하는 것을 좋아하기 때문에(복잡한 연산이 아니면 람다식이 더 보기 좋으니까!) 람다식으로 변경해서 다시 제출했다.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] arr = new int[n][2];
int count = 0;
int end = 0;
int temp = 0;
for(int i = 0; i < n; i++) {
arr[i][0] = sc.nextInt();
arr[i][1] = sc.nextInt();
}
Arrays.sort(arr, (int[] fst, int[] snd) -> {
if(fst[1] == snd[1]){
return fst[0] - snd[0];
}else{
return fst[1] - snd[1];
}
});
for(int i = 0; i < n; i ++){
if(end <= arr[i][0]){
end = arr[i][1];
count++;
}
}
System.out.println(count);
}
}
위에 있는 것이 람다식을 적용한 것이고
아래에 있는 것이 Comparator를 적용한 것이다.
확실히 람다식을 사용하는 것이 메모리를 조금 더 차지하지만 시간이 줄어드는 것과 코드 길이 자체가 짧아지는 것을 확인 가능하다. (근데 저정도 시간차가 유의미할까...?)