프로그래머스 코테연습 | 호텔대실

코딩테스트 연습 문제 LV.2 호텔 대실 - 문제 바로가기

문제 설명

• 호텔을 운영 중인 코니는 최소한의 객실만을 사용하여 예약 손님들을 받으려고 합니다. 한 번 사용한 객실은 퇴실 시간을 기준으로 10분간 청소를 하고 다음 손님들이 사용할 수 있습니다.
  예약 시각이 문자열 형태로 담긴 2차원 배열 book_time이 매개변수로 주어질 때, 코니에게 필요한 최소 객실의 수를 return 하는 solution 함수를 완성해주세요.

제한사항

• 1 ≤ book_time의 길이 ≤ 1,000
  • book_time[i]는 ["HH:MM", "HH:MM"]의 형태로 이루어진 배열입니다
    - [대실 시작 시각, 대실 종료 시각] 형태입니다.
  • 시각은 HH:MM 형태로 24시간 표기법을 따르며, "00:00" 부터 "23:59" 까지로 주어집니다.
    • 예약 시각이 자정을 넘어가는 경우는 없습니다.
    • 시작 시각은 항상 종료 시각보다 빠릅니다.

접근 방법

• 알고리즘 종류 : Greedy

• book_time은 [["15:00","17:00"], ["16:40", "18:20"]] 형식으로 구성되어 있으므로 먼저 timeInt 배열을 생성하여 모두 분으로 변경한다. 이 때 청소에 10분씩 걸리므로 end값에 10분도 더해줌.
  timeInt 예시 - [[800, 1030], [1000, 1110]]

• timeInt배열을 시작시간 기준으로 정렬, 동일한 경우 종료시간 기준으로 정렬해줌.

• PriorityQueue를 생성하여 현재 가장 빨리 퇴실하는 방의 퇴실시간보다 새로운 손님의 예약시간이 더 작을 경우 새로운 방 생성(que에 종료시간 추가, 방 생성)

• 그렇지 않을 경우 현재 가장 빨리 퇴실하는 방의 퇴실시간을 새로운 손님의 퇴실시간으로 변경(que에서 하나 꺼내고, 새로운 퇴실시간 추가)

import java.util.*;

class Solution {
    public int solution(String[][] book_time) {
    	//새로 시간을 가공해서 담을 배열
        int[][] timeInt = new int[book_time.length][2];
        
        for(int i=0; i<book_time.length; i++){
            timeInt[i][0] = Integer.parseInt(book_time[i][0].split(":")[0])*60+
                Integer.parseInt(book_time[i][0].split(":")[1]);
            timeInt[i][1] = Integer.parseInt(book_time[i][1].split(":")[0])*60+
                Integer.parseInt(book_time[i][1].split(":")[1])+10;
        }
        
        // 예약시간 기준으로 정렬, (동일한 경우 종료시간 기준 정렬)
        Arrays.sort(timeInt, (o1, o2) -> {
            if(o1[0]==o2[0]){
                return o1[1]-o2[1];
            }return o1[0]-o2[0];
        });
        
        // 무조건 방은 1개 있으므로 1부터 시작
        PriorityQueue<Integer> pq = new PriorityQueue();
        int answer = 1;
        pq.add(timeInt[0][1]);
        
        //방을 돌면서 새로운 방을 생성할지 원래 방에서 예약을 받을지 결정
        for(int i=1; i<timeInt.length; i++){
            if(timeInt[i][0]<pq.peek()){ //새로운 방을 받아야하는 경우
                pq.add(timeInt[i][1]);
                answer++;
            }else{ //원래 있던 방을 받을 경우
                pq.poll();
                pq.add(timeInt[i][1]);
            }
        }
        return answer;
    }
}

정렬방법에 대해서 . . .

보통 코딩테스트 문제에서 정렬을 해야하는 경우가 자주 나오는데 정렬에 대해 정리해보자.

자바 7 이하

오름차순 정렬 시

• 리스트 정렬 시 -> Collections.sort();
• Primitive type 정렬시 -> Arrays.sort(); ( 단, 역순정렬은 primitive타입 불가)

* Primitive type - int, double과 같은 소문자로 시작하는 타입, 참조 자료형이 아닌 타입

사용자 정의 정렬

• Comparator (@Override compare)
• Comparable (@Override compareTo)

자바 8 부터

• comparator 나 comparable 대신 람다문법 지원.

Arrays.sort(timeInt, (o1, o2) -> {
            if(o1[0]==o2[0]){
                return o1[1]-o2[1];
            }return o1[0]-o2[0];
        });

# Thinking

대체로 Comparator나 Comparable 사용방법을 자주 까먹어서 문서를 찾아보고는 했는데 람다문법은 잊지 않을 수 있을 것 같다. 그래도 두 정렬방법의 정의나 차이점, 사용법은 꼭 기억해야 하므로 다음에 한번 다뤄보도록 해야지.