문제 설명
접근 방법
문제에서 요구하고있는 회의실을 사용할 수 있는 회의의 최대 개수를 구하기 위해서는 우선 가장 일찍 시작하는 회의 시간에서 가장 늦게 시작하는 회의 시간 까지 겹치지 않으면서 사이사이에 가능한한 회의들이 다닥다닥 붙어있어야 합니다.
이러한 환경(?)을 만들기 위해 우선 입력받은 회의실 정보를 '끝나는 시간'을 기준으로 오름차순 정렬하고 만일 같다면 '시작 시간'을 기준으로 오름차순 정렬합니다.
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
List<MeetingRoom> meetingRooms = new ArrayList<>();
StringTokenizer st;
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
meetingRooms.add(new MeetingRoom(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
}
Collections.sort(meetingRooms);
// (...생략...)
}
static class MeetingRoom implements Comparable<MeetingRoom> {
int startTime;
int endTime;
public MeetingRoom(int startTime, int endTime) {
this.startTime = startTime;
this.endTime = endTime;
}
@Override
public int compareTo(MeetingRoom o) {
if (o.endTime < endTime) {
return 1;
}
else if (o.endTime > endTime) {
return -1;
}
if (o.startTime < startTime) {
return 1;
}
else if (o.startTime > startTime) {
return -1;
}
return 0;
}
}
이렇게 정렬한 후에 만일 첫 번째 회의의 끝나는 시간에 대해 두 번째 회의의 시작 시간이 같거나 크다면 이는 가장 연이어 할 수 있는 회의일 것입니다. 이후 이전과 같은 방법으로 두 번째 회의의 끝나는 시간에 대해 세 번째 회의의 시작 시간을 비교하여 동일한 작업을 반복해줍니다.
int count = 1, endTime = meetingRooms.get(0).endTime;
for (int i = 1; i < n; i++) {
if (endTime <= meetingRooms.get(i).startTime) {
count++;
endTime = meetingRooms.get(i).endTime;
}
}
System.out.println(count);
전체 소스 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
class Main {
static class MeetingRoom implements Comparable<MeetingRoom> {
int startTime;
int endTime;
public MeetingRoom(int startTime, int endTime) {
this.startTime = startTime;
this.endTime = endTime;
}
@Override
public int compareTo(MeetingRoom o) {
if (o.endTime < endTime) {
return 1;
}
else if (o.endTime > endTime) {
return -1;
}
if (o.startTime < startTime) {
return 1;
}
else if (o.startTime > startTime) {
return -1;
}
return 0;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
List<MeetingRoom> meetingRooms = new ArrayList<>();
StringTokenizer st;
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
meetingRooms.add(new MeetingRoom(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
}
Collections.sort(meetingRooms);
int count = 1, endTime = meetingRooms.get(0).endTime;
for (int i = 1; i < n; i++) {
if (endTime <= meetingRooms.get(i).startTime) {
count++;
endTime = meetingRooms.get(i).endTime;
}
}
System.out.println(count);
}
}
참고자료
'Algorithm > BOJ' 카테고리의 다른 글
[백준 - 1238] 파티 - Java (0) | 2022.05.13 |
---|---|
[백준 - 1018] 체스판 다시 칠하기 - Java (2) | 2022.05.12 |
[백준 - 7569] 토마토 - Java (0) | 2022.05.04 |
[백준 - 11047] 동전 0 - Java (0) | 2022.04.18 |
[백준 - 2805] 나무 자르기 - Java (0) | 2022.04.15 |