[백준] 1374번 강의실

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

1374번: 강의실

우선순위 큐를 활용해야 한다.

 

핵심

시작 시간이 빠른 순으로 정렬 후에 우선큐에서 현재 진행 중인 강의 중 종료 시간이 가장 빠른 강의를 비교한다.

진행 중인 강의의 end값이 다음 강의 start보다 크면 강의실 개수를 1 늘리고, 큐에 다음 강의를 넣는다.

반대의 경우 강의실 1개를 제거한다. 코드를 통해 알아보자.

 

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

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());
        List<Time> times = new ArrayList<>();
        for (int i = 0; i < n; i++){
            String[] info = br.readLine().split(" ");
            times.add(new Time(Integer.parseInt(info[0]), Integer.parseInt(info[1]), Integer.parseInt(info[2])));
        }
        Collections.sort(times);

        PriorityQueue<Integer> q = new PriorityQueue<>();

        int max = 1;

        for (int i = 0; i < n; i++){
            while (!q.isEmpty() && q.peek()<=times.get(i).start){
                q.poll();
            }
            q.offer(times.get(i).end);
            max = Math.max(max, q.size());
        }


        System.out.println(max);
    }

}


class Time implements Comparable<Time>{
    int num;
    int start;
    int end;

    @Override
    public int compareTo(Time t){
        if (this.start == t.start)return this.end - t.end;
        return this.start - t.start;
    }

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

해설

앞서 말한 대로 Time 클래스를 시작 시간순으로 compareTo를 재정의하였다.

이후 정렬한 뒤, 우선순위큐를 통한 반복문을 실행한다.

진행 중인 강의 -> 큐에 담겨있는 값들

진행 중인 강의들의 끝나는 시간이 다음 강의의 시작시간보다 작다면, 강의실을 비우게 된다. -> q.poll()

반대로 아직 끝나지 않았다면 큐에서 제거하지 못하고, 다음 강의를 큐에 넣는다. 

이때 큐의 사이즈를 확인한다 -> 강의실의 개수

이를 반복하고, 큐의 사이즈가 가장 큰 순간이 필요한 강의실의 수이다.

 

 

배운 점

처음에는 visited배열을 사용하여, 수업을 1사이클 진행 후 아직 수업을 못한 강의들을 다시 반복하는 식으로 하였다.

이러한 방법을 사용하니 시간초과가 나오게 되었다. 우선순위 큐를 활용하니 적은 시간에 문제를 풀 수 있었다.

문제를 풀수록 사고력이 중요하다는 것을 느끼는 것 같다.

많이 풀고 성장하자.