설명
한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들려고 한다.
각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라.
단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.
입력
첫째 줄에 회의의 수 n(1<=n<=100,000)이 주어진다. 둘째 줄부터 n+1 줄까지 각 회의의 정보가 주어지는데
이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 회의시간은 0시부터 시작한다.
회의의 시작시간과 끝나는 시간의 조건은 (시작시간 <= 끝나는 시간)입니다.
출력
첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.
예시 입력 1
5
1 4
2 3
3 5
4 6
5 7
예시 출력 1
3
예시 입력 2
3
3 3
1 3
2 3
예시 출력 2
2
내가 작성한 문제 이해
선생님 문제 이해
다른 건 나와 같고,
💡 나는 : 인덱스i의 끝시간 ≤ 인덱스i+1의 첫시간이라면, cnt++
—> 문제점 인덱스를 어떻게 뽑을 것인가 이슈 존재
선생님: 비교값으로 쓰일 tmp 선언 후 0으로 초기화,
t.f ≥ tmp 면 cnt++ 그리고 tmp를 t.l로 변경
case1. tmp 변경을 첫시간으로 하는 경우
import java.util.*;
class Time implements Comparable<Time> {
int f,l;
// 매개변수가 있는 생성자
Time(int f, int l) {
this.f = f;
this.l = l;
}
// 오버라이드, compareTo를 통한 정렬
@Override
public int compareTo(Time t) {
// 끝시간이 같을 때, 첫시간 오름차순 정렬 this- t
if(this.l == t.l) {
return this.f - t.f;
}else {
// 끝시간 오름차순 this- t
return this.l - t.l;
}
}
}
public class Conference {
public int solution(ArrayList<Time> arr) {
int cnt =0;
// 임시값 0 초기화
int tmp = 0;
for(Time t : arr) {
if(t.f >= tmp) {
cnt++;
// 제일 중요 : tmp = t.f과 결과 비교
tmp = t.f;
}
}
return cnt;
}
public static void main(String[] args) {
Conference T = new Conference();
// 입력 두 번 받음 : 총n, ArrayList로 n만큼
Scanner kb = new Scanner(System.in);
int n = kb.nextInt();
// ArrayList 선언
ArrayList<Time> arr = new ArrayList<>();
// for문 돌면서 입력받음
for(int i=0; i<n; i++) {
int f = kb.nextInt();
int l = kb.nextInt();
arr.add(new Time(f,l));
}
// 정렬 : 끝시간으로 정렬되어짐
Collections.sort(arr);
// 넘겨줌
System.out.println(T.solution(arr));
}
}
tmp = t.f; 으로 했을 때 에러 발생 케이스 분석
i)
입력값
5
1 4
2 3
3 5
4 6
5 7
리턴값
4
정닶값
3
ii)
입력값
5
3 3
1 3
2 3
4 6
5 7
리턴값
5
정답값
3
case2. tmp 변경을 끝시간으로 하는 경우(정답)
import java.util.*;
class Time implements Comparable<Time> {
int f,l;
// 매개변수가 있는 생성자
Time(int f, int l) {
this.f = f;
this.l = l;
}
// 오버라이드, compareTo를 통한 정렬
@Override
public int compareTo(Time t) {
// 끝시간이 같을 때, 첫시간 오름차순 정렬 this- t
if(this.l == t.l) {
return this.f - t.f;
}else {
// 끝시간 오름차순 this- t
return this.l - t.l;
}
}
}
public class Conference {
public int solution(ArrayList<Time> arr) {
int cnt =0;
// 임시값 0 초기화
int tmp = 0;
for(Time t : arr) {
if(t.f >= tmp) {
cnt++;
// 제일 중요 : tmp = t.f과 결과 비교
tmp = t.l;
}
}
return cnt;
}
public static void main(String[] args) {
Conference T = new Conference();
// 입력 두 번 받음 : 총n, ArrayList로 n만큼
Scanner kb = new Scanner(System.in);
int n = kb.nextInt();
// ArrayList 선언
ArrayList<Time> arr = new ArrayList<>();
// for문 돌면서 입력받음
for(int i=0; i<n; i++) {
int f = kb.nextInt();
int l = kb.nextInt();
arr.add(new Time(f,l));
}
// 정렬 : 끝시간으로 정렬되어짐
Collections.sort(arr);
// 넘겨줌
System.out.println(T.solution(arr));
}
}
💡적절히 tmp만들어서 최솟값, 최댓값, 0으로 초기화하고 비교값으로 사용하는 게 중요!