https://www.acmicpc.net/problem/1931
이 문제는 그리디 카테고리에 있는 문제이다.
핵심
이 문제의 핵심은 어떻게 배정을 해야 많은 사람이 이용할 수 있을까?이다.
끝나는 시간이 빠른 순서대로 정렬을 하고 그에 맞게 회의실에 넣어주면 된다.
코드를 보면 쉽게 이해할 수 있다.
정답 코드
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
List<Conference> list = new ArrayList<>();
for (int i = 0; i < N; i++) {
Conference conference = new Conference(sc.nextInt(), sc.nextInt());
list.add(conference);
}
list.sort(new Comparator<Conference>() {
@Override
public int compare(Conference o1, Conference o2) {
if (o1.getEnd() != o2.getEnd()) {
return o1.getEnd() - o2.getEnd();
} else {
return o1.getStart() - o2.getStart();
}
}
});
int count = 0;
int endTime = -1;
for (int i = 0; i < N; i++){
if (list.get(i).getStart()>=endTime) {
endTime = list.get(i).getEnd();
count++;
}
}
System.out.println(count);
}
}
class Conference {
private int start;
private int end;
public int getStart() {
return start;
}
public int getEnd() {
return end;
}
public Conference(int start, int end) {
this.start = start;
this.end = end;
}
}
해설
가장 중요한 포인트는 끝나는 시간이 빠른 순서대로 정렬이 돼야 한다는 것이다.
Conference라는 클래스를 만든 이유는 이러한 방식이 더 편하다고 생각되기 때문이다.
이제 앞서 말한 대로 끝나는 시간이 빠른 순으로 정렬을 한다. 만약 값이 같다면 시작시간이 빠른 순으로 정렬한다.
시작 시간이 이전에 끝난 시간보다 늦거나 같다면 그 회의를 참여시킨다.
배운 점
이전에 이와 비슷한 문제를 풀어본 적이 있어서 쉽게 풀 수 있었다.
처음에는 이중배열을 사용할까 고민하였지만, 클래스를 한 개 더 만드는 것이 직관이라 생각하였고,
스스로도 이러한 방법이 더 편해서 위와 같은 코드가 나왔다.
'PS > 알고리즘 문제풀이' 카테고리의 다른 글
[백준] 10986번 나머지 합(java) (0) | 2023.02.06 |
---|---|
[백준] 11286번 절댓값 힙(java) (1) | 2023.02.04 |
[SWEA] 10507번 영어 공부- 투 포인터(java) (0) | 2023.02.02 |
[백준] 2138번 전구와 스위치(java) (3) | 2023.02.02 |
[SWEA] 13736번 사탕 분배 - 분할 정복(java) (0) | 2023.02.02 |