[JAVA]1374 강의실

 📚 문제  

1374번: 강의실

🔍 아이디어  

최대한 적은 강의실을 사용하여 모든 수업을 할 수 있도록 하는 문제입니다.

처음 문제를 읽었을때는 그리디 문제로 생각하고 끝시간을 기준으로 정렬하고 모든 경우를 확인하였으나 그렇게 하면 시간 초과가 발생합니다. 

 

다른 문제 풀이방법은 강의를 입력받는 경우 시작시간, 끝 시간을 구분하여 입력받고 시작시간인 경우에는 필요한 강의실이 하나 증가, 끝 시간인 경우는 필요한 강의실이 하나 감소하도록 하여 한 시점에 최대 몇개의 강의실이 필요한지 세면 됩니다. (동시간에 필요한 최대 회의실 개수입니다)

 

정렬시에는 시간을 기준으로 정렬하지만 강의가 끝난 강의실을 먼저 - 하고 그 다음에 시작하는 강의실을 + 할 수 있도록 하기 위해서 정렬 조건에서 만약 시간이 같은 경우 끝나는 경우가 먼저 리턴 될수 있도록 하였습니다.

 

만약 위의 정렬조건을 하지 않은 경우 아래와 같은 입력이 있다면 

4
1 1 2
2 2 3
1 1 2
2 2 3

가 큐에 들어가면 아래와 같이 정렬될 수 도 있습니다.

Lecture{time=1, isStart=true}
Lecture{time=1, isStart=true}
Lecture{time=2, isStart=true}
Lecture{time=2, isStart=false}
Lecture{time=2, isStart=false}
Lecture{time=2, isStart=true}
Lecture{time=3, isStart=false}
Lecture{time=3, isStart=false}

먼저 끝났수업이라고 판단 된것을 처리하지 않아 필요한 강의실이 3개로 출력됩니다.

따라서 먼저 끝나는 경우를 처리해준 이후에 시작하는 경우를 처리해주기 위해 정렬조건을 추가로 넣어서 진행해야 합니다.

정렬 조건이 추가된 이후에는 2개의 강의실이 필요하다고 출력됩니다.

 

📝 풀이 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Boj_1374_강의실 {
    private static class Lecture implements Comparable<Lecture> {
        int time;
        boolean isStart;

        public Lecture(int time, boolean isStart) {
            this.time = time;
            this.isStart = isStart;
        }

        @Override
        public int compareTo(Lecture other) {
            if (this.time == other.time) {
                if(!this.isStart) return -1; //끝 -> 시작순으로 진행 하도록 하기 위해서
                return 1;
            }
            return time - other.time;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        PriorityQueue<Lecture> all = new PriorityQueue<>();

        while (n-- > 0) {
            st = new StringTokenizer(br.readLine());
            st.nextToken();
            all.add(new Lecture(Integer.parseInt(st.nextToken()), true)); //시작
            all.add(new Lecture(Integer.parseInt(st.nextToken()), false)); //끝
        }

        int classCnt = 0;
        int minClassCnt = 0;
        while (!all.isEmpty()) {
            Lecture lecture = all.poll();
            if (lecture.isStart) {
                classCnt++; //시작 수업이다 ( 강의실이 하나 더 필요하다)
            } else {
                classCnt--; //끝나는 수업이다 (강의실 하나 이제 안 필요하다)
            }
            minClassCnt = Math.max(classCnt, minClassCnt);
        }
        System.out.println(minClassCnt);
    }
}

 

또한 이문제는 우선순위 큐를 이용해서도 아래와 같이 풀이 할 수 있습니다.

(위와 유사한 풀이지만 우선순위 큐를 이용하여 동시간에 몇개의 수업이 있는지 확인합니다)

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

public class Boj_1374_강의실_pq {
    private static class Lecture implements Comparable<Lecture> {
        int start;
        int end;

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

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        PriorityQueue<Lecture> lectures = new PriorityQueue<>();

        while (n-- > 0) {
            st = new StringTokenizer(br.readLine());
            st.nextToken();
            lectures.add(new Lecture(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        int minClassCnt = 0;
        PriorityQueue<Integer> currentLectures = new PriorityQueue<>(); //끝나는 시간만 넣는다.
        while (!lectures.isEmpty()) {
            Lecture lecture = lectures.poll();

            //해당 수업 시간 전에 끝난 수업이 있으면 뺀다.
            while (!currentLectures.isEmpty() && currentLectures.peek() <= lecture.start) {
                currentLectures.poll();
            }

            //시작시간이 같은 수업이 있다면 넣는다.
            currentLectures.add(lecture.end);
            while (!lectures.isEmpty() && lectures.peek().start == lecture.start) {
                currentLectures.add(lectures.poll().end);
            }

            //현재 큐의 사이즈가 현재 시간에 필요한 회의실의 수 이다.
            minClassCnt = Math.max(currentLectures.size(), minClassCnt);
        }
        System.out.println(minClassCnt);
    }
}