[백준] 1379 - 강의실 2 (Java)

문제 파악

https://www.acmicpc.net/problem/1379

풀이

우선순위 큐를 써야겠다!
보통 이런 문제들은 큐를 많이 써 큐의 크기를 반환해주는 경우가 경험상 많다.

[강의실 번호, 강의가 끝나는 시간] 으로 구성된 우선순위 큐를 만들어 주자.
이 때 강의가 끝나는 시간을 오름차순으로 정렬해주도록 설정한다.

주어진 강의를 강의 시작 시간 오름차순으로 정렬한다.
정렬된 강의를 돌며 우선순위 큐에 넣어주기를 반복하면 된다.
큐를 업데이트하는 과정은 다음과 같다.

• 들어갈 수 있는 강의실이 없는 경우 큐에 원소를 추가한다.
• 수업을 마치고 재활용할 수 있는 방이 있다면 업데이트 해 큐에 다시 넣어준다.

추가로 예시에 주어진 답안과 똑같지 않아도 통과되기에 너무 겁먹지 않고 제출해도 된다.. 허허
다만 문제가 살짝 불친절해서 정답은 강의 번호 오름차순으로 출력해주어야 한다는 점을 숙지하자😅

코드

import java.io.*;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int lectureCount = Integer.parseInt(br.readLine());
        Queue<int[]> roomQueue = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        int[] answer = new int[lectureCount];
        ArrayList<int[]> lectures = new ArrayList<>();
        for (int l = 0; l < lectureCount; l++) {
            String[] line = br.readLine().split(" ");
            int lectureNo = Integer.parseInt(line[0]) - 1;
            int lectureStartTime = Integer.parseInt(line[1]);
            int lectureEndTime = Integer.parseInt(line[2]);
            lectures.add(new int[]{lectureNo, lectureStartTime, lectureEndTime});
        }
        lectures.sort(Comparator.comparingInt(a -> a[1]));
        int totalRoomCount = 0;
        for (int[] lecture : lectures) {
            if (!roomQueue.isEmpty() && roomQueue.peek()[1] <= lecture[1]) {
                int[] availableRoom = roomQueue.poll();
                roomQueue.offer(new int[]{availableRoom[0], lecture[2]});
                answer[lecture[0]] = availableRoom[0];
            } else {
                roomQueue.offer(new int[]{totalRoomCount, lecture[2]});
                answer[lecture[0]] = totalRoomCount;
                totalRoomCount++;
            }
        }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.append(String.valueOf(totalRoomCount)).append("\n");
        for (int a : answer) {
            bw.append(String.valueOf(a + 1)).append("\n");
        }
        bw.flush();
    }
}