[Day19]JAVA 백준 강의실(1374번)

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

 

---

🌘 문제 이해하기

• N개의 강의가 있다.
• 강의의 시작하는 시간과 끝나는 시간을 알고 있다.
• 한 강의실에서는 동시에 2개 이상의 강의를 진행할 수 없고 , 한 강의의 종료시간과 다른 강의의 시작시간이 겹치는 것은 상관없다.
• 강의번호 , 시작시간 , 종료시간  입력이 꼭 순서대로 주어지지 않을 수 있으나 한 번씩만 주어진다. 
• 필요한 최소 강의실의 수를 출력하라

---

🌗 문제 자세히보기

 

1. 하나의 강의에 대해서 강의번호  , 시작시간 , 종료시간을 저장하기 위해서는 lectures 라는 클래스를 생성해서 해당 정보들을 넣어준다. 

강의를 순서대로 진행하기 위해서는 강의의 시작시간 , 종료시간 으로 정렬이 되어 있어야 한다.  

그래서 Comprable 의 compareTo 를 사용해서 시작시간 순으로 , 시작시간이 동일하다면 종료시간으로 정렬될 수 있도록 오버라이딩 한다.

 

class lectures implements Comparable<lectures>{

    int classNum;
    int startTime;
    int endTime;

    lectures(int num , int start, int end)
    {
        this.classNum = num;
        this.startTime = start;
        this.endTime = end;
    }

    @Override
    public int compareTo(lectures o)
    {
        if(this.startTime == o.startTime)
        {
            return this.endTime - o.endTime;
        }

        return this.startTime - o.startTime;
    }
}

 

2. 모든 강의에 대한 정보를 담을 List를 위에서 생성한 lectures 타입으로 생성한다.

List<lectures> TimeTable = new ArrayList<>();
  
for(int i=0;i<n;i++)
    {
        st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        TimeTable.add(new lectures(a, b, c));
    }

 

아무렇게나 입력된 TimeTable 를 정렬하면 아래처럼 정렬된다. 

Collections.sort(TimeTable);

 

3. 현재 강의 중인 강의실을 저장할 PriorityQueue를 생성해준다. 

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

 

PriorityQueue 를 사용하는 이유는 강의의 종료 시간을 효율적으로 관리 할 수 있기 때문이다. 

 

3번 강의는 2 에 시작해서 14 에 끝난다.

1번 강의는 3 에 시작해서 8 에 끝난다.

즉, 3번 강의가 먼저시작하지만 1번강의가 먼저 끝나서 1번이 사용한 강의실 더 먼저 빈 강의실이 되기 때문에 입력과 상관없이 끝나는 시간이 우선순위로 관리 되어야 한다. 

 

4. TimeTable 에 저장된 모든 강의를 순차적으로 아래 순서로 추가 

• 현재 진행 중인 강의실이 없으면 PriorityQueue  에 추가
• 새로운 강의 의 시작시간이  현재 진행 중인 강의가 끝나는 시간보다 크거가 같다면 현재 진행 중인 강의 PriorityQueue 에서 제거

        -   새로운 강의 시작시간 >= 현재 진행 중인 강의 끝나는 시간

• 새로운 강의 PriorityQueue 에 추가 
• 한 강의가 추가될때마다 현재 진행 중인 강의실 개수를 구한다.(최대값을 유지하기 위해)

for(lectures l : TimeTable)
{
    //현재 진행중인 강의에서 비교 
    //새롭게 시작 할 강의 의 시작시간이 끝나는 시간보다 크면 해당 강의실에서 강의
    while(!que.isEmpty() && que.peek() <= l.startTime)
    {
        que.poll();
    }

    que.offer(l.endTime);//끝나는 시간으로 저장

    result = Math.max(result,que.size());          

}

 

---

🌕 최종코드

import java.io.*;
import java.util.*;
public class Main{

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

        PriorityQueue<Integer> que = new PriorityQueue<>();//현재 강의 중인 강의실

        int n = Integer.parseInt(br.readLine()); //n개의 강의실
      
        List<lectures> TimeTable = new ArrayList<>();

        for(int i=0;i<n;i++)
        {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            TimeTable.add(new lectures(a, b, c));
        }

        Collections.sort(TimeTable);

        int result = 0;

        //3. 강의실 배정
        for(lectures l : TimeTable)
        {
            //현재 진행중인 강의에서 비교 
            //새롭게 시작 할 강의 의 시작시간이 끝나는 시간보다 크면 해당 강의실에서 강의
            while(!que.isEmpty() && que.peek() <= l.startTime)
            {
                que.poll();
            }

            que.offer(l.endTime);//끝나는 시간으로 저장
           
            result = Math.max(result,que.size());          
           
        }

        System.out.println(result);
    }   
}

//1. 강의실 정보 담은 Class 생성
class lectures implements Comparable<lectures>{

    int classNum;
    int startTime;
    int endTime;

    lectures(int num , int start, int end)
    {
        this.classNum = num;
        this.startTime = start;
        this.endTime = end;
    }

    @Override
    public int compareTo(lectures o)
    {
        if(this.startTime == o.startTime)
        {
            return this.endTime - o.endTime;
        }

        return this.startTime - o.startTime;
    }
}