[백준-1931번 자바/java] 회의실 배정 _디버깅의 눈물
https://www.acmicpc.net/problem/1931
1931번: 회의실 배정
(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.
www.acmicpc.net
회의실 배정 성공
| 2 초 | 128 MB | 143237 | 44767 | 31663 | 29.563% |
문제
한 개의 회의실이 있는데 이를 사용하고자 하는 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) 를 이용할 수 있다.
체크 포인트
1. 그리디 알고리즘(Greedy Algorithm) 이용
-현재의 가장 최적의 답을 선택해 적합한 결과를 도출해내는 '그리디 알고리즘'을 이용하는 문제이다.
-그리디 알고리즘의 대표적 문제 유형으로는 활동 선택 문제나 거스름돈 문제 등이 있다. 이 문제처럼 스케줄을 최대한 많이 배정하는 문제가 활동 선택 문제 유형에 해당한다.
-'회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다'라는 조건에서 그리디 알고리즘의 조건을 확인할 수 있다.
2. 회의 종료 시간이 빠른 순으로 정렬(Comparator 정렬 활용)
// Comparator를 이용한 2차원 배열 오름차순 정렬
Arrays.sort(arr, new Comparator<Integer[]>() {
@Override
public int compare(Integer[] o1, Integer[] o2) {
// 회의 종료 시간이 동일한 경우,
if(o1[1] == o2[1]){
// 회의 시작 시간을 기준으로 비교 후 오름차순 정렬
return o1[0] - o2[0];
}
// 회의 종료 시간이 다른 경우,
else{
// 회의 종료 시간을 기준으로 오름차순 정렬
return o1[1] - o2[1];
}
}
});
-최대 사용할 수 있는 회의의 최대 개수를 구하려면 회의 종료 시간이 빠른 순서로 정렬해야 한다.
-종료시간이 빠를 수록 주어진 회의 시간 내 더 많은 회의를 진행할 수 있기 때문이다.
-Comparator와 람다식을 이용한 2차원 배열 정렬을 이용해 오름차순 정렬을 할 수 있다.
-회의 종료시간을 기준으로 오름차순 정렬 후, 만약 회의 종료시간이 동일하다면 회의 시작시간을 기준으로 오름차순 정렬을 진행했다.
https://tears-of-debugging.tistory.com/54
[java(자바)] 2차원 배열 정렬하기 Comparator, 람다식 _디버깅의 눈물
2차원 배열 정렬하기 Comparator, 람다식 -2차원 배열을 정렬할 때 1)Comparator를 이용한 방법과 2)람다식을 이용한 방법 두 가지를 활용할 수 있다. 1)Comparator를 이용한 이차원 배열의 정렬 int[][] arr = {{
tears-of-debugging.tistory.com
3. 이전 회의 종료 시간(prevEnd)과 현재 회의 시작 시간(startPoint)이 겹치지 않도록 한다.
// 이전 회의 종료시간을 담아주는 변수
prevEnd = arr[0][1];
// 시작 시 회의 개수 1 추가 처리
count++;
// 0번 이후 회의부터 카운팅 시작
for(int i=1; i<N; i++){
// 회의 시작 시간
startPoint = arr[i][0];
// 현재 회의 시작 시간이 이전 회의 종료 시간보다 크거나 같은 경우,
if(startPoint>=prevEnd){
// 회의 개수 추가
count++;
// 이전 회의 종료 시간 = 현재 회의 종료 시간
prevEnd = arr[i][1];
}
}
-한 회의가 끝나가 다음 회의가 시작될 수 있다는 조건을 충족하기 위해 조건이 필요하다.
-제일 첫 회의는 직접 변수를 입력하고, 두번째 회의(i=1)부터는 for문을 통해서 조건을 비교 후 count 처리를 진행했다.
풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int prevEnd,startPoint,count;
static Integer[][] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// 회의의 수
int N = Integer.parseInt(st.nextToken());
// 회의 시작 시간과 끝나는 시간을 담는 2차원 배열
arr = new Integer[N][2];
// 회의 시간 입력
for(int i=0; i<N; i++){
st = new StringTokenizer(br.readLine(), " ");
arr[i][0] = Integer.parseInt(st.nextToken());
arr[i][1] = Integer.parseInt(st.nextToken());
}
solution(N);
}
static void solution(int N){
// Comparator를 이용한 2차원 배열 오름차순 정렬
Arrays.sort(arr, new Comparator<Integer[]>() {
@Override
public int compare(Integer[] o1, Integer[] o2) {
// 회의 종료 시간이 동일한 경우,
if(o1[1] == o2[1]){
// 회의 시작 시간을 기준으로 비교 후 오름차순 정렬
return o1[0] - o2[0];
}
// 회의 종료 시간이 다른 경우,
else{
// 회의 종료 시간을 기준으로 오름차순 정렬
return o1[1] - o2[1];
}
}
});
// 이전 회의 종료시간을 담아주는 변수
prevEnd = arr[0][1];
// 시작 시 회의 개수 1 추가 처리
count++;
// 0번 이후 회의부터 카운팅 시작
for(int i=1; i<N; i++){
// 회의 시작 시간
startPoint = arr[i][0];
// 현재 회의 시작 시간이 이전 회의 종료 시간보다 크거나 같은 경우,
if(startPoint>=prevEnd){
// 회의 개수 추가
count++;
// 이전 회의 종료 시간 = 현재 회의 종료 시간
prevEnd = arr[i][1];
}
}
System.out.println(count);
}
} // end of Main