백준 1374번 - 강의실 [JAVA]

TaeBong·2022년 12월 13일

Java 골드5 백준 우선순위큐

알고리즘 풀이

목록 보기

5/14

🧩 문제

▶ 백준 1374 강의실 바로가기

N개의 강의가 있다. 우리는 모든 강의의 시작하는 시간과 끝나는 시간을 알고 있다. 이때, 우리는 최대한 적은 수의 강의실을 사용하여 모든 강의가 이루어지게 하고 싶다.

물론, 한 강의실에서는 동시에 2개 이상의 강의를 진행할 수 없고, 한 강의의 종료시간과 다른 강의의 시작시간이 겹치는 것은 상관없다. 필요한 최소 강의실의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 번호는 1부터 N까지 붙어 있으며, 입력에서 꼭 순서대로 주어지지 않을 수 있으나 한 번씩만 주어진다. 강의 시작 시간과 강의 종료 시간은 0 이상 10억 이하의 정수이고, 시작 시간은 종료 시간보다 작다.

출력

첫째 줄에 필요한 최소 강의실 개수를 출력한다.

예제

입력

출력

🎯 풀이

메모리	시간	코드길이
59736 KB	4048 ms	2142 B

풀이

입력받은 강의들은 우선순위 큐를 이용하여 시작시간을 기준으로 오름차순으로 정렬하며 강의실은 강의가 끝나는 시간을 기준으로 우선순위 큐를 사용하였다. rooms의 시간(종료 시간)이 현재 강의 시작 시간 이하라면 현재 강의 종료 시간으로 대체해주고, 초과라면 rooms에 새로운 강의실을 만들어주는 형식이다. 모든 강의들을 강의실에 배정시키고 난 후 rooms의 크기를 출력해주면 답을 도출할 수 있다.

⭐️ 전체 풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BJ1374_강의실 {

    private static class Lecture implements Comparable<Lecture> {
        int no, start, end;

        public Lecture(int no, int start, int end) {
            this.no = no;
            this.start = start;
            this.end = end;
        }

        @Override
        public int compareTo(Lecture o) {
            return this.start - o.start;
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());

        PriorityQueue<Lecture> lectures = new PriorityQueue<>();

        //입력받기
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int no = Integer.parseInt(st.nextToken());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            lectures.add(new Lecture(no, start, end));
        }

        //종료시간을 기준으로 하는 방을 정렬
        PriorityQueue<Integer> rooms = new PriorityQueue<>();
        rooms.add(lectures.poll().end);

        while(!lectures.isEmpty()) {
            int roomsCnt = rooms.size();
            Lecture curLecture = lectures.poll();
            boolean isPossible = false;

            for(int i = 0; i < roomsCnt; i++) {
                //강의하고 있는 강의실에서 강의를 할 수 있다면
                if(rooms.peek() <= curLecture.start ) {
                    rooms.poll();   //현재 강의실에서의 강의를 제거
                    rooms.add(curLecture.end);  //다음 강의의 종료시간 넣기
                    isPossible = true;
                    break;
                }
            }
            if(!isPossible) rooms.add(curLecture.end);
        }

        System.out.println(rooms.size());

    }   //main 함수 끝
}