[BOJ 11000] 강의실 배정 - JAVA

그리디 문제인 강의실 배정을 풀어보았습니다.

골드 문제는 처음이라서 그런지 생각해야할 것이 많더라구요..

이 방법은 개인적인 방법이며 최적의 솔루션이 아닐 수 있습니다.

구현 내용

 

구현 방법

가장 중요한 구현 방법은 Sorting의 방법입니다.

 

N개의 강의를 강의 시작 시간과 끝나는 시간을 비교하여 최소의 강의실을 배정해야하기 때문입니다.

그러기 위해선 강의를 시작시간 기준으로 정렬해야합니다.

또한, PriorityQueue를 이용하여 끝나는 시간을 기준으로 먼저 끝나는 강의실을 비교할 수 있도록 합니다.

 

강의를 시작시간 기준으로 정렬햐여하는 이유는 끝나는 시간 기준으로 정렬을 한다면

4

1 3

2 6

3 8

6 7

다음과 같은 예제에서 문제가 생깁니다.

3 8이 1 3 뒤에 붙고

6 7이 2 6 뒤에 붙어야 최소 강의 실이 나옵니다. 하지만 끝나는 시간을 기준으로 한다면

1 3

2 6

6 7

3 8 순으로 들어오게 되고 6 7이 1 3뒤에 붙어 3 8이 따로 강의실을 배정받게 되어 최소 강의실이 나오지 않게 됩니다.

 

자세한 설명은 주석을 통해 하도록 하겠습니다.

↓↓↓↓↓↓↓↓↓↓↓↓↓    ↓↓↓↓↓↓↓↓↓↓↓↓↓↓    ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

class Node implements Comparable<Node>{
    int a;
    int b;
    Node(int a, int b){
        this.a = a;
        this.b = b;
    }
    int getA(){
        return this.a;
    }
    int getB(){
        return  this.b;
    }

    @Override
    public int compareTo(Node o) {  //서류등수 정렬
        return this.getA() - o.getA();
    }
}
public class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 입력
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        // 출력

        int result = 0; //결과
        StringTokenizer stok;
        int n = Integer.parseInt(br.readLine());    //수업의 개수
        ArrayList<Node> node = new ArrayList<>();   //강의 시간 리스트
        for(int i=0;i<n;i++) {
            stok = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(stok.nextToken());
            int b = Integer.parseInt(stok.nextToken());
            node.add(new Node(a,b));
        }
        Collections.sort(node); //강의 시작 시간을 기준으로 정렬
        PriorityQueue<Integer> q = new PriorityQueue<>();   //강의가 먼저 끝나는 순서대로
                                                            //정렬하기 위해 PQ 사용
        int data = node.get(0).getB();      //가장 먼저 시작하는 강의의 끝나는 시간
        q.add(data);    //QUEUE에 저장한다.
        for(int i=1;i<n;i++){   //수업의 개수만큼 반복문
           if( q.peek() > node.get(i).getA()){  //가장 먼저 끝나는 수업시간보다
               q.offer(node.get(i).getB());     //다음 수업시간이 빠르다면 QUEUE에 저장
           }
           else{    //가장 먼저 끝나는 수업시간보다 다음 수업시간이
                    // 같거나 느리다면 앞 수업시간 뒤에 붙힌다
               q.poll();    //앞의 수업시간 QUEUE에서 제외
               q.offer(node.get(i).getB()); //다음 수업시간 QUEUE에 추가
           }
        }
        result = q.size();  //QUEUE에 남아있는 수업개수 == 최소 강의실
        bw.write(String.valueOf(result));

        bw.flush();
    }
}