문제 해석
문제
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
입력
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.
문제 풀이
무식하게 풀 수 있을까?
무식하게 풀기 - 회의실 사용 가능한 모든 경우의 수 중 가장 많은 경우를 출력한다.
회의 수가 10만이나 입력되기 때문에 아마 모든 경우를 구하기는 메모리제한이 있어서 어려울 것 같다.,
💰그리디 알고리즘 이용
💰 그리디 알고리즘이란?
답을 여러 조각으로 쪼개고, 각 단계마다 지금 당장 가장 좋은 방법만을 선택하는 알고리즘
많은 경우 해를 찾아낼 수 없음, 제한된 경우에서만 사용된다.
그럼에도 그리디 알고리즘을 사용하는 이유?
동적 계획법이나 완전 탐색법보다 훨씬 빠르기 때문에!
속도가 빨라서 그냥 이거 쓸 수 있으면 쓰는게 좋다..
그리디 알고리즘 사용되는 경우
-
탐욕법을 사용해도
항상 최적해를 구할 수 있는 문제를 만난 경우 -
시간이나 공간적 제약으로 인해
최적해를 찾기 너무 어려우면그냥 대충 탐욕법으로 괜찮은 답을 찾음
✨ 그리디 알고리즘의 정당성 증명
탐욕적인 알고리즘이 항상 최적해를 찾아낼 수 있다는 것을 아래 두가지 속성을 증명함으로써 보일 수 있다!
1. 탐욕적 선택 속성
각 단계에서 탐욕적으로 내리는 선택이 항상 최적해로 가는 길 중 하나이며,
탐욕적 선택이 손해가 없다!를 증명
가장 종료 시간이 빠른 회의를 포함하는 최적해가 반드시 존재한다.- 가장 일찍 끝나는 회의를 선택해서 최적해를 얻는 것이 불가능해지는 경우는 없음!
2. 최적 부분 구조
- 부분 문제의 최적해에서 전체 문제의 최적해를 만들 수 있음을 증명
대개 자명해서 따로 증명할 필요가 없음!
그리디 알고리즘을 이용한 풀이 구성
구상하기
회의실 배정이 가장 많은 경우는 회의시간이 짧은 회의부터 착착 배정하면 가장 많은 회의를 찾을 수 있을 것 같음
-
제일 가까운 시간이면서 -
회의시간이짧은회의
따라서, 가장 가까운 시간에 시작하는 회의 중 끝나는 시간이 제일 빠른 회의를 선택!
시간만으로 회의실을 배정하는 경우는 아래처럼 되어 해답을 찾을 수 없다.
- 짧은 하나의 회의를 긴 두회의 대신 잡아버림,,
- 그럴듯하다고 해서 정답이 아니라 쓰기가 까다로움.. 0.ㅠ 항상 정당성 증명이 필요하다!
구현하기
✨ 한 회의를 선택할 때마다 겹치는 회의 모두 제거하는 방법
- 모든 회의를 종료시간 오름차순으로 정렬
- 정렬된 회의를 순회하면서 앞 회의와 겹치지 않는 회의 찾기
💡 오름차순 정렬 - Java Arrays.sort 고치기!
sort 방식 커스텀하는 방법은 크게 두가지!
-
Comparable을 class에 implememt 한 후,compateTo메소드를 override -
sort내부에서
comparator를 사용하고,compare메소드를 override
나는 2번이 편해서 2번을 선택해서 풀이를 진행했다.
Comparator 정의
-
정렬 가능한 클래스들의
기본 정렬 기준과 다르게 정렬하고 싶을 때 사용하는인터페이스 -
package: java.util.Comparator
-
주로 익명 클래스로 사용됨
-
기본 정렬 방법인 오름차순 정렬을 내림차순으로 정렬할 때 많이 사용
Comparator 구현 방법
-
comparator interface를
implements -
compare()메서드 오버라이드 한myComparatorclass 작성-->
익명 클래스로도 작성 가능, 아래 코드에서는 익명 클래스로 작성하였음
compare() 메소드 작성법
-
첫번째 파라미터로 넘어온 객체 < 두번째 파라미터로 넘어온 객체:
음수리턴 -
첫번째 파라미터로 넘어온 객체 == 두번째 파라미터로 넘어온 객체:
0리턴 -
첫번째 파라미터로 넘어온 객체 > 두번째 파라미터로 넘어온 객체:
양수리턴
✨ 음수 또는 0이면 객체 자리 유지되며,
양수인 경우 두 객체의 자리가 변경된다.
Arrays.sort(timetable, 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];
}
});-
o1[1]==o2[1] : 두개 끝나는 시간이 같을 경우
-
return o1[0] - o2[0]
1) o1의 시작하는 시간이 더 빠르면음수--> 둘의 위치 바뀌지 않음,
2) o1의 시작하는 시간이 더 크면양수--> 둘의 위치 바뀜
--> 더 시작시간이 빠른 게 앞으로 정렬됨 -
return o1[1] - o2[1]
두개 끝나는 시간 비교해서 o1이 더 빨리 끝날 경우 자리 변경 없고, 더 늦게 끝날 경우 o2와 자리 바뀜
문제 풀이 코드
package Greedy;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class BOJ1931 {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int N = s.nextInt();
int[][] timetable = new int[N][2];
for (int i = 0; i < N; i++) {
timetable[i][0] = s.nextInt();
timetable[i][1] = s.nextInt();
}
//timetable 정렬 다시 정의
Arrays.sort(timetable, 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];
}
});
int result = 0;
int end_time = 0;
for (int i = 0; i < N; i++) {
if (timetable[i][0] >= end_time) {
end_time = timetable[i][1];
result++;
}
}
System.out.println(result);
}
}
