1931번: 회의실 배정
(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.
www.acmicpc.net
📖 문제
그리디 알고리즘의 대표적인 예시 문제라고 해도 될 문제입니다. 그래서 풀이에 대해서 조금 정리해보려고 합니다.
🔎 접근 방법
- 회의 일정에는 시작 시간과 종료 시간이 존재합니다.
- 회의 일정은 겹치면 안되고, 최대한 많은 회의를 진행해야 합니다.
위 조건을 생각해봤을 때, 이전 회의 일정의 종료 시간과 겹치지 않아야 하고 이후 일정의 시작 시간과 겹치지 않아야 합니다.
즉, 회의 일정을 종료 시간 기준으로 오름차순 정렬하여 종료 시간이 빠른 일정부터 해결해나가면 정답에 접근할 수 있습니다.
1. 회의 일정을 저장할 수 있는 클래스 선언 후 Comparable 구현하기
배열을 사용하는 풀이도 많았지만 가장 직관적이고 자바라는 언어 특성을 사용할 수 있도록 Meeting 클래스를 만들어 객체의 비교 기준을 정의할 수 있는 Comparable를 구현해 줬습니다.
class Meeting implements Comparable<Meeting> {
int start;
int end;
public Meeting(int start, int end) {
this.start = start;
this.end = end;
}
@Override
public int compareTo(Meeting obj) {
// 종료 시간이 동일하다면 시작 시점이 빠른 순으로 정렬
if (this.end == obj.end) {
return this.start - obj.start;
}
// 종료 시점이 빠른 순으로 회의 일정을 정렬
return this.end - obj.end;
}
}start와 end는 회의의 시작 시간과 종료 시간이고, Comparable을 구현하기 위한 compareTo() 메소드를 보면 정렬 조건을 확인할 수 있습니다.
위에서는 정렬 조건을 종료 시간만을 언급했지만, 문제에서 "회의의 시작시간과 끝나는 시간이 같을 수도 있다."란 조건이 존재하기 때문에 회의 시작 시간도 신경 써줘야 합니다. 반례를 한번 생각해 볼까요
[입력]
4
3 5
1 3
8 8
5 8
위처럼 만약 입력이 들어왔다고 했을 때, 정답이 몇일까요? 정답은 4입니다. 하지만 회의의 종료 시간만을 고려해서 정렬하게 되면 3이라는 결과를 얻을 수도 있습니다. 어떻게 3이 나올 수 있었을까요. 회의의 종료시간을 기준으로 정렬을 해보겠습니다.
Meeting A(1, 3) -> Meeting B(3, 5) -> Meeting C(8, 8) -> Meeting D(5, 8)
회의의 종료 시간을 오름차순으로 정렬했습니다. 이제 처음 데이터부터 확인하면서 회의 일정을 확인해 보면 아래와 같습니다.
1시 - 3시 : Meeting A
3시 - 5시 : Meeting B
8시 - 8시 : Meeting C
Meeting D의 시작 시간인 5시가 이전 미팅 Meeting C의 종료 시간 8시보다 작기 때문에 이어서 회의를 진행할 수 없습니다.
이런 반례가 발생할 수 있기 때문에 해당 문제는 회의의 종료 시간도 오름차순으로 정렬해줘야 하고, 회의 종료 시간이 같을 때는 시작 시간으로 오름차순 정렬을 해줘야 합니다.
2. 입력받은 데이터로 Meeting 인스턴스 만들어서 PriorityQueue에 넣기
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
PriorityQueue<Meeting> meetings = new PriorityQueue<>();
int n = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
meetings.offer(new Meeting(start, end));
}Meeting 인스턴스를 저장해서 바로 우리가 정의한 Comparable의 정렬 조건대로 정렬하기 위해서 우선순위 큐(Priority Queue)를 사용했습니다. 물론 ArrayList를 사용해서 Collections.sort()를 사용해 줘도 됩니다.
3. Priority Queue의 Meeting 객체를 하나씩 꺼내오면서 이전 Meeting의 종료 시간과 비교하여 정답을 확인
Meeting prevMeeting = meetings.poll();
int answer = 1; // 가장 처음 회의 일정은 추가되기 때문에 1부터 시작
while (!meetings.isEmpty()) {
Meeting meeting = meetings.poll();
// 현재 회의 시작 시간이 이전 회의 일정의 종료 시간과 동일하거나 크면 정답에 추가
if (prevMeeting.end <= meeting.start) {
answer++;
// 현재 회의를 이전 회의로 지정
prevMeeting = meeting;
}
}
System.out.println(answer);prevMeeting(이전 회의)에 가장 우선순위가 높은 회의 일정을 하나 넣어줍니다. N은 1 이상이기 때문에 비어있는 검사를 하지 않고 바로 poll()을 사용해서 넣어줬습니다. 방금 꺼내준 회의 일정은 바로 추가되기 때문에 answer는 1로 초기화합니다.
그리고 이제 Priority Queue가 비워질 때까지 반복문을 돌면서 회의 일정을 확인합니다. 만약 이전 회의의 종료 시간보다 현재 회의의 시작 시간이 크거나 같다면 정답 카운트를 증가시키고, prevMeeting를 다시 현재 회의 meeting으로 갱신합니다.
🧑🏻💻 전체 코드
import java.io.*;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
PriorityQueue<Meeting> meetings = new PriorityQueue<>();
int n = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
meetings.offer(new Meeting(start, end));
}
Meeting prevMeeting = meetings.poll();
int answer = 1; // 가장 처음 회의 일정은 추가되기 때문에 1부터 시작
while (!meetings.isEmpty()) {
Meeting meeting = meetings.poll();
// 현재 회의 시작 시간이 이전 회의 일정의 종료 시간과 동일하거나 크면 정답에 추가
if (prevMeeting.end <= meeting.start) {
answer++;
// 현재 회의를 이전 회의로 지정
prevMeeting = meeting;
}
}
System.out.println(answer);
}
}
class Meeting implements Comparable<Meeting> {
int start;
int end;
public Meeting(int start, int end) {
this.start = start;
this.end = end;
}
@Override
public int compareTo(Meeting obj) {
// 종료 시간이 동일하다면 시작 시점이 빠른 순으로 정렬
if (this.end == obj.end) {
return this.start - obj.start;
}
// 종료 시점이 빠른 순으로 회의 일정을 정렬
return this.end - obj.end;
}
}'🧑🏻💻 Dev > 알고리즘' 카테고리의 다른 글
| [백준] 1967번 트리의 지름 (Java) (0) | 2023.06.07 |
|---|---|
| [백준] 1238번 파티 (Java) (0) | 2023.06.05 |
| [백준] 1260번 DFS와 BFS 자바 (0) | 2023.04.28 |
| [프로그래머스] 혼자서 하는 틱택토 Java (0) | 2023.03.20 |
| [프로그래머스] 레벨 1 문제 모두 풀고난 후 배운점 (2) | 2023.03.17 |
