호텔 대실 (자바, 프로그래머스)

풀이 아이디어

• priority queue 자료구조 활용

우선, 객실 대여 시간이 정렬되어있지 않아서 ArraList를 새로 선언해서 대여 시간을 정렬. 이렇게 해야 객실을 대여해줄 때 이미 선점하고 있는 방을 줄 수 있는지 확인 가능하다
(예를 들어 14:30~15:30 , 14:00~15:00 순으로 입력이 들어오면 14:30 기준으로 방을 먼저 대여해주게 되기 때문)
다음으로 객실 대여해줄 때마다 객실 반납 시간을 추가할 때마다 자동 정렬시키기 위해 PriorityQueue 사용.
만약, 객실 대여해줄 때 반납된 객실이 있다면 방을 추가하지 않고,
객실 대여해줄 때 방이 모두 차 있으면 방 추가

import java.util.*;

class Solution {
    public int solution(String[][] book_time) {
        int answer = 0;
//         반납 시간을 넣어줄 때마다 오름차순으로 저장
        PriorityQueue<Integer> pq = new PriorityQueue<>((Integer o1, Integer o2) -> (o1 - o2));
        
//         대여 시간을 오름차순으로 저장
        ArrayList<int[]> list = new ArrayList<>();
        for(String[] book : book_time){
            int[] e = new int[2];
            e[0] = parse_time(book[0]);
            e[1] = parse_time(book[1]);
            list.add(e);
        }
        Collections.sort(list, (int[] o1, int[] o2) -> o1[0] - o2[0]);
    
        for(int[] e : list){
            int start = e[0];
            int end = e[1];
            Integer prev = pq.peek();
            // System.out.println("prev: "+prev);
            if(prev == null || prev > start){
                pq.add(end+10);
                answer += 1;
            }else if(prev != null && prev <= start){
                pq.poll();
                pq.add(end+10);
            }
            // for(Integer k : pq){
            //     System.out.print(k+" ");
            // }
            // System.out.println();
        }
        return answer;
    }
    
    public int parse_time(String time){
        String[] parsed = time.split(":");
        int rtime = 0;
        rtime += Integer.parseInt(parsed[0])*60;
        rtime += Integer.parseInt(parsed[1]);
        return rtime;
    }
}