백준 11000 <강의실 배정>

알고리즘 중 내가 어렵다고 생각한 그리디 부분의 문제이다.

 

이 문제에서 생각할 것은 얼마나 많은 수업이 겹치냐!이다.

 

그리디로 밖에 풀 수 없는 이유는 S와 T의 범위가 10의 9승으로 모든 N개 범위가 0부터 10의 9승이라면

 

10의 9승 곱하기 20만= 즉 엄청난 숫자가 되므로 당연히 X

 

다른 방법으로 N을 종료 시간 순으로 정렬해서 계속 비교해주게 된다면 N의 제곱! 20만의 제곱으로 시간을 마찬가지

 

로 터지게 된다. X 

 

이 문제가 다른 문제에 비해 까다로웠던 이유는! 두 가지 단계를 거쳐 판단해야 했기 때문이다.

 

이 문제의 순서는 두 단계이다.

1. 시작시간으로 정렬
2. 우선순위 큐를 사용하여 종료시간이 짧은 순으로 나올 수 있게 한다!!

여기서 2번의 우선순위 큐를 사용한다고 생각을 하게 되는 것이 가장 어려웠다.

 

이렇게 5개의 수업시간표가 있다고 가정하면 시작시간 기준으로 정렬을 해서 이전 값 들이 자신의 시작시간보다 작은지 판단 이게 총단계이다

 

 

여기서 우선순위 큐를 사용하여 이전의 값들을 관리하게 되는 이유는 그냥 큐를 사용할 경우

 

2번째의 종료시간이 자신의 시작 시간보다 늦기 때문에 빠져나오지 못하고 그다음의 종료시간은 자신의 시작시간보다 빠름에도 불구하고 2번째 시간이 큐에서 나오지 못하기 때문에 아무 의미 없이 교실을 하나 더 개설하게 된다.!

 

여기서 중요한 점은!! 그래서 이전까지 값들을 종료 시간순으로 우선순위 큐를 하는 것!!!

 

이 문제가 많은 것을 배울 수 있었던 이유 하나는 비교를 다른 값으로 해주기 위해 comparator을 사용했다는 점!

 

일단 우선순위 큐를 해주기 위해 comrable을 이용해 종료시간을 비교해주기 위해 ti라는 클래스를 새로 선언!

 

이 부분은 시작시간을 기준으로 정렬해주기 위해 익명으로 comrator을 사용하여 정렬 한 부분이다!

 

진짜 이문제는 이게 핵심이었다... 불타올랐다.

 

그다음은 앞에서 말했던 것처럼 시작 순으로 정렬했기 때문에!! 우선순위 큐의 값들을 확인해서 빼주고 넣는 작업을 해서 max 값을 재설정해주면 문제는 끝!!

 

그리디 문제.. 아직 접근하기 너무 어렵다..

 

전체 코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main{
   public static class ti implements Comparable<ti>{
      int start;
      int finish;
      public ti(int start, int finish) {
         this.start = start;
         this.finish = finish;
      }
      @Override
      public int compareTo(ti o) {
         // TODO Auto-generated method stub
         return this.finish-o.finish;
      }   
   };
   static PriorityQueue<ti> pq;
   static int n,result;
   static ti table[];
   public static void main(String[] args) throws IOException {
      BufferedReader kb=new BufferedReader(new InputStreamReader(System.in));
      n=Integer.parseInt(kb.readLine());
      table=new ti[n];
      pq=new PriorityQueue<ti>();
      for(int i=0;i<n;i++) {
         StringTokenizer st=new StringTokenizer(kb.readLine());
         table[i]=new ti(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
      }
      Arrays.sort(table, new Comparator<ti>() {
         @Override
         public int compare(ti o1, ti o2) {
            // TODO Auto-generated method stub
            return o1.start-o2.start;
         }
      });
      for(int i=0;i<table.length;i++) {
         while(!pq.isEmpty()&&pq.peek().finish<=table[i].start) {
            pq.remove();
         }
         pq.add(table[i]);
         result=Math.max(result,pq.size());
      }
      System.out.println(result);
      
   }
}