백준 11000(강의실 배정) - Python(파이썬) - 그리디,정렬(heap, lambda,Comparator)

11000번: 강의실 배정

예제 설명

위상 정렬 참고

CHAPTER 6 -번외 정렬 - 위상 정렬(Topology Sort) - Python(파이썬)

	1	2	3	4	5
1-3
2-4
3-5

일단 1-3 ,2-4 ,3-5 을 처음 시작하는 시간으로 오름차순 정렬하고 그 담에 끝나는 시간으로 오름차순 정렬한다.

1시부터 3시, 3시부터 5시는 같은 강의실 배정이 가능 | 2시부터 4시 다른 강의실 배정

따라서 총 2개의 강의가 필요하다

 

좀 더 이해하기 쉽게 하기 위해서 ( 2 5 )( 1 3 )( 1 2 )( 3 9 ) 이 예시를 이용한다고 가정해보자

	1	2	3	4	5	6	7	8	9
1-2
1-6
2-5
3-9

1. 들어온 수를 처음 시작하는 시간 - > 끝난는 시간으로 정렬

2. 1-2가 들어오면 끝나는 시간 2를 따로 heap에 저장 ( 힙 : [ 2 ] )

3. 1-6가 들어오면 (heap[0] = 2)와 (시작하는 시간 = 1)을 비교한다. 이 때 비교 시 시작하는 시간이 1의 값이 heap[0]의 값보다 작으므로 같은 강의실에 들어올 수 없다.

따라서 Heap에 끝나는 시간( 6 )을 저장한다.

( 힙이므로 2보다 6이 더 커서 [ 2,6 ]으로 인덱스 0에는 2 인덱스 1에는 6을 저장)

4. 2-5가 들어오면 (heap[0]=2)와 (시작하는 시간=2)를 비교한다. 이 때 비교 시 시작하는 시간이 2의 값이 heap[0]의 크거나 같으므로 같은 강의실에 들어올 수 있다.

따라서 heap[0]의 값을 pop하고, heap에 5를 저장한다.

( 힙이므로 5보다 6이 작으므로 [ 5,6 ]으로 인덱스 0에는 5 인덱스 1에는 6을 저장)

5. 3-9가 들어오면 (heap[0]=5)와 (시작하는 시간=3)을 비교한다. 이 때 비교 시 시작하는 시간이 3의 값이 heap[0]의 값보다 작으므로 원래 있던 강의실에 들어올 수 없다. 

따라서 heap에 끝나는 시간 (9)를 저장한다.

( 힙이므로 9가 5,6 값보다 크므로 [5,6,9]으로 인덱스 0: 5, 인덱스 1:6, 인덱스 2:9가 저장)

6. 그러므로 힙의 길이의 값을 출력한다.

 

📌 접은 글에는 lambda 설명 

* 파이썬 ( 참고 자료 : https://dailyheumsi.tistory.com/67 )

1. sorted( ) : 리스트 아이템의 각 요소 순서대로 정렬 ( array[ i ][ 0 ] -> array[ i ][ 1 ])
2. key = lambda x : __ : key 인자에 함수를 넘겨주면 해당 함수의 반환값을 비교하여 순서대로 정렬
   1. 즉 , __ 안의 값으로 비교
   2. ex ) key = lambda x : x[ 1 ] 을 할 경우
      

      

3. key = lambda x : ( x[ 0 ], -x[ 1 ] ) : 첫번째 인자를 기준으로 오름차순 정렬하고, 두 번째 인자를 기준으로 내림차순으로 정렬 

x[0]의 값이 1인 경우(주황색) -> x[1]의 값을 비교하여 내림차순으로 정렬한다(노란색)

---

문제 설명

① array의 값을 정렬시킨 후에 heap에 array의 처음값을 입력한다.
② 인덱스 1부터 n-1까지 시작하는 시간,끝나는 시간을 입력받는다.
  1. heap[0]의 값 > 시작하는 시간 : heap에 끝나는 시간 입력
  2. else: heap[0]의 값 pop하고 heap에 끝나는 시간 입력
③ heap의 길이 출력

💻 Python( 파이썬 )

import sys
import heapq
#강의실 수업 입력
n = int(sys.stdin.readline())
array=[]
heap =[]
#강의실 입력
for i in range(n):
    array.append(list(map(int,sys.stdin.readline().split())))

#강의실 시작하는 시간 -> 끝나는 시간으로 정렬
array.sort()
#heap에 끝나는 시간 입력
heapq.heappush(heap,array[0][1])

for i in range(1,len(array)):
	#힙에 있는 처음값이 시작하는 시간보다 큰 경우 -> 새로운 강의실 필요
    if heap[0]>array[i][0]:
        heapq.heappush(heap,array[i][1])
    #힙에 있는 처음값이 시작하는 시간보다 작거나 같은 경우 -> 원래 있던 Heap pop하고, 강의실 다시 입력
    else:
        heapq.heappop(heap)
        heapq.heappush(heap,array[i][1])

#heap의 길이 출력
print(len(heap))

💻 Java(자바)

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        //heap 구현
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        //강의실 입력
        int[][] array = new int[n][2];
        StringTokenizer st;
        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine()," ");
            array[i][0]=Integer.parseInt(st.nextToken());
            array[i][1]=Integer.parseInt(st.nextToken());
        }
        //입력 데이터를 오름차순으로 정렬( 시작하는 시간이 같을 경우, 끝나는 시간을 기준으로 정렬
        Arrays.sort(array, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                //시작하는 시간이 같을 경우 -> 끝나는 시간의 차이를 출력
                if(o1[0]==o2[0]) return o1[1]-o2[1];
                return o1[0]-o2[0];
            }
        });
        heap.offer(array[0][1]);
        for(int i=1;i<n;i++){
            if(heap.peek()>array[i][0]){
                heap.offer(array[i][1]);
            }else{
                heap.poll();
                heap.offer(array[i][1]);
            }
        }
        System.out.println(heap.size());
    }
}