[백준] 알고리즘 분류(그리디 알고리즘,JAVA)11000번, 강의실 배정

문제 링크

11000번: 강의실 배정

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. T₁ <= S₂일 경우 같은 강의실을 사용할 수 있습니다.

2. 모든 수업을 진행하는데 사용하는 최소 강의실 개수를 결과로 출력합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 수업 시간을 정렬한 뒤 우선순위 큐로 강의실의 시간을 관리합니다.

 

3. 모든 수업에서 사용한 강의실의 개수를 결과로 출력합니다.

 

정렬.

 

강의실은 시작 시간이 작은 수업부터 진행하기 때문에 S를 오름차순.

 

S가 같을 때에는 T가 작은 시간으로 오름차순 정렬을 진행하였습니다.

 

강의실 배정.

 

PriorityQueue를 이용하여 현재 사용중인 강의실에 끝나는 시간을 저장하여 배정합니다.

 

예를 들어.

 

1 22 53 5

 

1 2일 때 사용할 수 있는 강의실이 존재하지 않으므로 강의실 새로 배정!

2(끝나는 시간)

강의실 1.

2 5일 때 시작하는 시간보다 작거나 같은 끝나는 시간을 가진 강의실 존재 : 강의실 1

강의실 끝나는 시간 ≤ 2

강의실 1에 수업 배정

5(끝나는 시간)

강의실 1.

3 5일 때 시작하는 시간보다 작거나 같은 끝나는 시간을 가진 강의실 존재하지 않음 : 새로운 강의실 배정

강의실 끝나는 시간 ≤ 3

 

5(끝나는 시간)	강의실 1.
5(끝나는 시간)	강의실 2.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 3

 

1 3
2 4
3 5

 

2. 수업 시간을 정렬한 뒤 우선순위 큐로 강의실의 시간을 관리합니다.

 

수업 시간 정렬!

S	T
1	3
2	4
3	5

우선순위 큐로 강의실 배정!

 

1 3 강의실 배정

사용할 수 있는 강의실이 존재하지 않으므로 강의실 새로 배정!

3(끝나는 시간)

강의실 1.

 

2 4일 때 시작하는 시간보다 작거나 같은 끝나는 시간을 가진 강의실 존재하지 않음 : 새로운 강의실 배정

강의실 끝나는 시간 ≤ 2

3(끝나는 시간)	강의실 1.
4(끝나는 시간)	강의실 2.

 

3 5일 때 시작하는 시간보다 작거나 같은 끝나는 시간을 가진 강의실 존재 : 강의실 1

강의실 끝나는 시간 ≤ 3

강의실 1에 수업 배정

4(끝나는 시간)	강의실 2.
5(끝나는 시간)	강의실 1.

 

3. 모든 수업에서 사용한 강의실의 개수를 결과로 출력합니다.

 

강의실 2까지 존재.

2을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 강의 시간을 나누었습니다.
• Arrays.sort를 이용하여 강의 시간 기준으로 정렬을 진행하였습니다.
• PriorityQueue과 강의 시간을 이용하여 강의실을 배정하였습니다.
• 모든 수업에 관하여 강의실을 배정한 후 강의실의 개수(Queue.size)를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

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


public class Main {
    //강의 수업 관련 클래스
    static class time implements Comparable<time>{
        int start, end;
        public time(int start, int end){
            this.start = start;
            this.end = end;
        }
        //수업 관련 오름차순 정렬
        @Override
        public int compareTo(time o) {
            if(this.start == o.start)
                return this.end - o.end;
            return this.start  - o.start;
        }
    }
    static int N;
    //강의실 배정에 사용할 PriorityQueue
    static PriorityQueue<Integer> pq = new PriorityQueue<>();
    //강의 시간 저장 배열
    static time[] arr;
    public static void main(String[] args) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        arr = new time[N];
        //강의 시간 저장
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine()," ");
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            arr[i] = new time(s, e);
        }
        Arrays.sort(arr);		//강의 시간 정렬
        pq.add(arr[0].end);	//첫 강의 강의실 배정
        //나머지 강의 강의실 배정
        for(int i=1;i<N;i++){
            //강의실 끝나는 시간 ≤ 현 강의 시작 시간일 때
            if(arr[i].start >= pq.peek())
                pq.poll();
            //강의실 추가 배정
            pq.add(arr[i].end);
        }
        bw.write(pq.size() + "");	//사용한 강의실 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}