[백준/11000] 강의실 배정 (Java)

Question


문제 해설

  1. Si에 시작해서 Ti에 끝나는 N개의 수업이 주어짐
  2. 모든 수업을 가능하게하는 최소 강의실의 개수는?



Solution

풀이 접근 방법

  1. 최대한 많은 강의 진행하는 문제 ~ -> "끝나는 시간 오름차순 정렬"이라고 생각하고 풀면 틀림!!

    1. 끝나는 시간 오름차순은 하나의 강의실에서 최대한 많은 수업을 진행하려할 때 해당됨!!
  2. 강의실이 비는 시간을 최소화 해야 함 = 강의 끝나는 시간과 다음 강의 시작 시간 사이의 텀이 작아야 함

    1. 강의 시간 오름차순 정렬해서 끝나는 대로 빨리 시작하는 강의 넣어야 함
    2. 반례 확인
  3. 강의 시간 오름차순 -> 강의 정보 객체(Session Class) 만들어서 우선순위 큐에 넣고 하나씩 뺌

  4. 빨리 끝나는 강의 알기 위해 -> 강의 끝나는 시간을 우선순위 큐에 넣고 관리


정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
  static class Session implements Comparable<Session> {
    int start, end;

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

    @Override
    public int compareTo(Session o) {
      // 시작시간 오름차순
      if (Integer.compare(this.start, o.start) == 0) {
        // 시작시간이 같다면, 종료시간 오름차순
        return Integer.compare(this.end, o.end);
      }
      return Integer.compare(this.start, o.start);
    }
  }

  static int N;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    N = Integer.valueOf(br.readLine());
    // 시간시간 오름차순 순서대로 강의 담음
    PriorityQueue<Session> sessions = new PriorityQueue<Session>();

    for (int i = 0; i < N; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      int start = Integer.valueOf(st.nextToken());
      int end = Integer.valueOf(st.nextToken());

      sessions.add(new Session(start, end));
    }

    // 강의실 개수 변수 : 1개로 시작
    int classCnt = 1;
    // 강의실별 끝나는 시간을 저장하는 큐 : 빨리 끝나는 강의싱이 우선순위 높음
    // 큐의 사이즈 = 오픈한 강의실 개수
    PriorityQueue<Integer> endQueue = new PriorityQueue<>();
    // 첫 강의실에서 진행하는 강의의 끝나는 시간 넣음
    endQueue.add(sessions.poll().end);

    // 모든 강의가 강의실에 들어갈 때 까지
    while (!sessions.isEmpty()) {
      Session current = sessions.poll();

      // 제일 빨리 끝나는 강의실의 종료 시간이 현대 시작해야할 강의보다 빠르면
      if (endQueue.peek() <= current.start) {
        // 해당 강의실 수업 종료
        endQueue.poll();
      } else {
        // 제일 빨리 끝나는 강의보다 시작 시간이 더 빠르면
        // 새로운 강의실 오픈
        classCnt++;
      }
      // 수업 종료한 강의실 || 새로 오픈한 강의실에 강의 넣음
      endQueue.add(current.end);
    }

    bw.write(classCnt + "\n");
    bw.flush();
    bw.close();
  }

}

좋은 웹페이지 즐겨찾기