728x90
| 19598번 / 최소 회의실 개수 |
❓ 최소 회의실 개수
🏷️ 관련 주제 : Greedy Sort Swipping PriorityQueue
💦 나의 시도
우선순위 큐(PriorityQueue)를 이용해 회의 시간 정렬하여 풀이 시도
변수 선언
- PriorityQueue<int[]>
meeting선언 : {회의 시작 시간, 회의 종료 시간}을 담은 1차원 int 배열을 담을 우선순위 큐- 사용자 지정 정렬 : 회의 시작 기준 오름차순, 회의 종료 시간 기준 오름차순
PriorityQueue<int[]> meeting = new PriorityQueue<>((a, b) -> (a[0] == b[0]) ? a[1] - b[1] : a[0] - b[0]); - ArrayList
rooms선언 : 현재 진행 중인회의의 종료 시간을 담을 ArrayList - int
minSize를 0으로 초기화 : 필요한 회의실 최솟값을 담을 정수형 변수
0 ~ (N - 1) 범위까지 반복문 실행하며 입력값 받기
입력값을 int[] time에 넣어 meeting에 추가하기
meeting에 원소가 존재하는 동안 반복문 실행하며 필요한 최대 회의실 개수 구하기
meeting에서 원소 꺼내서 int[]time에 할당 : 현재 가장 빨리 시작할 회의- 반복문을
rooms사이즈만큼 실행rooms의 원소 중 시작할 회의의 종료 시간time[0]보다 작은 값 모두 제거rooms에 시작할 회의의 종료 시간time[1]추가minSize에rooms의 크기와minSize중 더 큰 값 할당
결과값 minSize 출력
위의 방법으로 작성한 코드
import java.io.*;
import java.util.*;
public class Main
{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
PriorityQueue<int[]> meeting = new PriorityQueue<>(
(a, b) -> (a[0] == b[0]) ? a[1] - b[1] : a[0] - b[0]);
ArrayList rooms = new ArrayList<>();
int minSize = 0;
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int[] time = {Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
meeting.add(time);
}
while (!meeting.isEmpty()) {
int[] time = meeting.poll();
for (int i = 0; i < rooms.size(); i++) {
if (rooms.get(i) < time[0]) {
rooms.remove(i);
}
}
if (!rooms.isEmpty()) {
rooms.stream().filter(i -> i <= time[0]).forEach(rooms::remove);
}
rooms.add(time[1]);
minSize = Math.max(rooms.size(), minSize);
}
System.out.println(minSize);
}
}⏱️ 시간 초과
시간 초과 해결 방법이 마땅히 떠오르지 않아 다르게 풀이를 시도해 보았습니다.
회의를 순차적으로 진행, 진행하지 못한 회의를 ArrayList에 추가하고 모든 회의를 종료할 때까지 반복한 횟수를 결과값으로 출력
rooms 대신 ArrayList<int[]> meeting2를 선언
일단 최대한 진행할 수 있는 회의를 진행하고 중간에 진행할 수 없는 회의 시간은 meeting2에 추가
meeting의 원소가 존재하지 않으면 meeting2의 원소를 meeting에 옮겨 다시 회의 진행
이 과정을 meeting과 meeting2가 모두 빌 때까지 진행하고 총 반복 횟수를 결과값으로 출력
위의 방법으로 작성한 코드
import java.io.*;
import java.util.*;
public class Main
{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
PriorityQueue<int[]> meeting = new PriorityQueue<>(
(a, b) -> (a[0] == b[0]) ? a[1] - b[1] : a[0] - b[0]);
ArrayList<int[]> meeting2 = new ArrayList<>();
int rooms = 1;
int end = -1;
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int[] time = {Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
meeting.add(time);
}
while (!meeting.isEmpty() || !meeting2.isEmpty()) {
if (meeting.isEmpty()) {
rooms++;
end = -1;
meeting.addAll(meeting2);
meeting2.clear();
}
int[] time = meeting.poll();
if (time[0] < end) {
meeting2.add(time);
continue;
}
end = time[1];
}
System.out.println(rooms);
}
}⏱️ 시간 초과
다른 풀이 방법 시도
PriorityQueue에 진행한 회의의 종료 시간을 담고 진행할 회의 종료 시간 추가 및 종료된 회의를 삭제하여 우선순위 큐의 최대 크기 구하기(성공!)
- PriorityQueue
end선언 : 진행한 회의의 종료 시간을 담은 우선 순위 큐- 회의 종료 시간을 오름차순 정렬
- int
rooms를 1로 초기화 : 회의실 최소 개수를 담을 정수형 변수 meeting에 원소가 존재하는 동안 while문 실행meeting에서 원소를 하나 꺼내 int[]time에 할당 : 진행할 회의 시작 및 종료 시간end가 비어있으면, 회의 종료 시간time[1]추가 후, 반복문 처음으로 돌아감.- 진행할 회의의 시작 시간 전에 종료된 회의의 종료 시간 제거
while(!end.isEmpty() && end.peek() <= time[0]) { end.poll(); } end에 진행할 회의의 종료 시간 추가rooms에rooms와end의 크기 중 최댓값을 할당
rooms를 출력
📑제출 기록 및 오답 원인
💯 해결 방법
import java.io.*;
import java.util.*;
public class Main
{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
PriorityQueue<int[]> meeting = new PriorityQueue<>(
(a, b) -> (a[0] == b[0]) ? a[1] - b[1] : a[0] - b[0]);
PriorityQueue<Integer> end = new PriorityQueue<>();
int rooms = 1;
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int[] time = {Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
meeting.add(time);
}
while (!meeting.isEmpty()) {
int[] time = meeting.poll();
if (end.isEmpty()) {
end.add(time[1]);
continue;
}
while(!end.isEmpty() && end.peek() <= time[0]) {
end.poll();
}
end.add(time[1]);
rooms = Math.max(rooms, end.size());
}
System.out.println(rooms);
}
}728x90
