[PriorityQueue] 효율적인 스케줄링

https://school.programmers.co.kr/learn/courses/30/lessons/155651

프로그래머스

 

이 문제에서의 팁)

1. 위 문제는 이전 타임의 퇴실시각과 다음 타임의 입실시각을 비교해야 하는 문제로,

    입실시각을 기준으로 오름차순 정렬한 배열 & 퇴실시각을 기준으로 오름차순 정렬한 배열

     두가지의 배열이 필요하다.

 

 

import java.util.PriorityQueue;
import java.util.Arrays;
import java.util.Comparator;
class Solution {
    public int solution(String[][] book_time) {
        int answer = 0;
        int[][] bookTime = new int[book_time.length][2];       
        
        for(int i=0;i<book_time.length;i++){
            int start = Integer.parseInt(book_time[i][0].replace(":",""));
            int end = Integer.parseInt(book_time[i][1].replace(":",""));
            
            end+=10;			// 청소 시간
            
            if(end%100 >= 60){
                end+=40;        // ex) 1559+10 -> 1569 -> 1609 시간 단위로 변환
            }

            bookTime[i][0] = start;
            bookTime[i][1] = end;
        }
        
        // 첫번째 숫자(시작시각) 기준으로 오름차순 정렬
        Arrays.sort(bookTime, (a,b) -> a[0]-b[0]);
            
    
        // 두번째 숫자(종료시각) 기준으로 오름차순 정렬
        PriorityQueue<int[]> checkout = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        
        //[1410,1930]->[1420,1530]->[1500,1710] ->[1640,1830]->[1820,2130] 순서로 진행
        for(int[] book : bookTime){ 
            if(checkout.isEmpty()){
                checkout.add(book);
            }else{
                int[] temp = checkout.peek();
                int start = temp[0];
                int end = temp[1];
                
                if(book[0] >= end){		//다음 입실시각 >= 이전 퇴실시각
                    checkout.poll();		// 다른 방 배정할 필요가 없기 때문
                }
                
                checkout.add(book);
            }
        }
        
        // 반복문을 다 돈후, checkout에 남아있는 타임들은 앞에 다른 방의 타임들과 겹쳐서 남아있는 것들
        answer = checkout.size();
        return answer;
    }
}

 

1. 가장 빠른 첫타임(편의상 a)의 [시각시각,종료시각]을 checkout에 추가

2. 다음 타임의 시작시각(b) >= 이전 타임의 종료시각(a) 비교

3. 만족할 경우 이어서 방 배정이 가능하므로 이전타임(a) checkout에서 삭제

3-1. 만족하지 못할 경우 4번 실행

4. 다음 타임(b) checkout에 추가

5. 2번으로 돌아가서 반복

 

 

>  int[ ][ ] bookTime = new int[book_time.length][2]

: String 타입으로 나타낸 시간을 int 타입의 네자리 문자열로 바꾼 후,

   첫번째 숫자(대실 시작시각) 기준으로 오름차순 정렬한  배열

: 입실시각 기준 정렬

ex) "18:30" -> 1830 

 

>  PriorityQueue<int[]> checkout = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));

 : 위에서 만든 배열을 바탕으로 두번째 숫자(대실종료시각)를 기준으로 오름차순 정렬한 배열

 : 퇴실시각 기준 오름차순 정렬이므로, 가장빠른 퇴실시각이 peek가 됨.

 : 퇴실시각 기준 정렬

 

 

---

 

퇴실시각 기준 정렬은 PriorityQueue를 사용한 이유

일반적인 Queue(큐)는 FIFO(First-In-First-Out)를 따르지만 우선 순위에 따라 요소를 정렬하여 우선 순위가 가장 높은 요소 먼저 처리되도록 합니다.

 

자바 PriorityQueue는 보통 Heap을 이용하여 구현합니다.

따라서 데이터를 추가할 때,  우선 순위를 기준으로 Max Heap(최대 힙) 혹은 Min Heap(최소 힙)을 구성하고

데이터를 꺼내거나 삭제할 때는 적절한 자리를 찾아 옮기는 방식으로 진행됩니다.

 

• Max Heap (최대 힙) : 최대 값이 우선순위인 큐
• Min Heap (최소 힙) : 최소 값이 우선순위인 큐

 

bookTime에서의 뒤에 올 입실시각과 checkout의 이전 타임의 퇴실시각을 비교.

(checkout에 있는 이전타임들의 방 중 가장 빠른  퇴실시각 vs bookTime에 있는 다음타임의 가장 빠른 입실시각)

>>다음 타임을 위해 이전타임의 방들 중 가장 빠른 퇴실시각의 방을 배정해주는 것이 방 배정 개수를 최소화하는 방법이기 때문이다.

---

 

흐름을 정리해 보면 아래와 같다.

book
: 시작 시각 기준으로 오름차순 정렬
[1410  ,  1930] 
[1420  ,  1530]
[1500  ,  1710]
[1640  ,  1830]
[1820  ,  2130]

checkout 
: 종료 시각 기준으로 오름차순 정렬

 start      end
[1410  ,  1930] peek
			1420 >= 1930 (F)
[1420  ,  1530] peek
[1410  ,  1930] 
			1500 >= 1530 (F)
[1420  ,  1530] peek
[1500  ,  1710]
[1410  ,  1930] 
			1640 >= 1530 (T)
[1500  ,  1710] peek
[1410  ,  1930] 
[1640  ,  1830]
			1820 >= 1710 (T)
[1410  ,  1930] peek
[1640  ,  1830]
[1820  ,  2130]

bookTime 반복문 종료

 

 

 

 

[참고]

https://seasome1.com/%EC%9E%90%EB%B0%94-priorityqueue/