[백준] 11000 강의실 배정 - JAVA

★★☆

문제

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

11000번: 강의실 배정

풀이 시간 : 30분

풀이

초기 풀이 방향은 이랬다.

 

1. 먼저 강의를 시작시간을 기준으로 오름차순 정렬해야 한다. 최소한의 강의실을 써야 하기 때문이다.

2. 정렬한 강의를 순서대로 강의실 큐에 넣는다.

각각의 강의실 큐에서 마지막 강의의 끝나는 시간과 비교해서 강의가 가능한 강의실에 추가한다.

 

이렇게 진행하려 했는데 생각해보니 굳이 강의를 다 가지고 있을 필요 없이 강의실의 마지막 강의의 끝나는 시간만 알고 있어도 괜찮다는 것을 깨닫고 방법을 바꾸었다.

 

1. ArrayList에 강의실 강의가 끝나는 시간을 넣는다.

2. 정렬한 강의들을 하나하나 넣으면서 넣으려는 강의 시작시간이 해당 강의실의 강의가 끝나는 시간과 겹치지 않는다면 추가하고

빈 강의실이 없다면 리스트에 강의실을 추가한다.

 

근데!!!! 풀다보니 리스트로 풀면 안된다는 생각이 들었다.

강의가 먼저 시작한다 해도 무조건 해당 강의가 늦게 시작한 강의들보다 빨리 끝나는게 아니기 때문에 일반 ArrayList에 담는다면 계속 리스트를 정렬해주어야 했기 때문이다..

그래서 기존 ArrayList로 선언되었던 강의실 리스트를 우선순위 큐로 타입을 변경했고 잘 통과했다!

 

 

코드

import java.util.*;
import java.io.*;

/*
    강의실 배정
    골드 5
    시간 : 640ms
    메모리 : 73444kb
*/

public class Main {

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

        int N = Integer.parseInt(br.readLine());
        // 강의
        Lecture []lectures = new Lecture[N];

        // 강의실 큐
        PriorityQueue<Integer> queue = new PriorityQueue<>();

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            lectures[i] = new Lecture(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
        }

		// 시작시간 오름차순으로 정렬
        Arrays.sort(lectures, new Comparator<Lecture>() {
            @Override
            public int compare(Lecture o1, Lecture o2) {
                return o1.start-o2.start;
            }
        });

        queue.add(lectures[0].end);

        for (int i = 1; i < N; i++) {
            if(queue.peek()<=lectures[i].start) {
                queue.poll();
            }
            queue.add(lectures[i].end);
        }

        System.out.println(queue.size());
    }

    public static class Lecture {
        int start;
        int end;

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