[프로그래머스] 호텔 대실 JAVA

링크

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

풀이

예약 시간이 2차원 Array로 제공된다.

Task Scheduling 문제는 경우는 개인적으로 그리디로 푸는 경우가 많다.

배열의 길이는 최대 1000이므로, 허용되는 시간 복잡도가 N^2도 가능해진다.

즉, 2중 for문도 가능하다.

첫번째로 생각할 점은 제공되는 데이터의 포맷이다.

HH:mm 의 형태로 제공된다.

나는 이 형태의 데이터 포맷을 SimpleDateFormat 클래스의 parse 메서드를 통해 모든 데이터를 "분"으로 통일해주었다.

String의 형태로 비교해주어도 되지만, 청소시간인 10분을 더해줘야한다는 조건이 있기 때문에, 휴먼에러를 최소화 하며 계산하기 위해 포맷을 변경했다.

두번째로 생각할 점은 시작시간과 종료시간 중 기준을 어디로 잡을지이다.

어디로 잡던 풀이는 동일하기 때문에 시작시간으로 기준을 잡았다.

1. Data Format을 분으로 통일해준다.
2. int형으로 변환한 이차원 Array를 시작시간 기준으로 오름차순 정렬한다.
3. List<Integer>을 통해 방의 개수를 세어 준다.
   3-1. 해당 리스트에는 예약의 종료시간을 넣어준다.
   3-2. 리스트는 매 반복마다 오름차순 정렬을 해주어야한다.
4. list의 size를 반환한다.

3-2가 필요한 이유는 다음과 같다.
01:00-02:00 을 예약 -> 01:30-02:30 예약 -> 02:10-02:40 예약 하는 경우
다음 예약으로 02:50-03:30 시간대가 들어온다고 가정해보자.

현재 룸 1의경우 01:00-02:00, 02:10-02:40
룸2의 경우 01:30-02:30 이 들어가 있다.
오름차순정렬이 안되어 있다면 02:50-03:30의 예약은 종료시간이 가장 빠른 시간인 룸2가 아닌, 룸1로 예약되게 된다.

이러면 최적의 예약방법이 아니기 때문에 최소한의 방을 잡는게 불가능해질 수 있다.

그렇기 때문에 예약 로직의 매 반복마다 List를 오름차순 정렬해준다.

이게 비 효율적이긴 하지만, 시간 복잡도가 넉넉하기 때문에 가능하다.

코드

import java.util.*;
import java.text.SimpleDateFormat;
import java.io.*;

class Solution {
    
    private static long MINIUTES_STANDARD = (1000 * 60);
    private static SimpleDateFormat format = new SimpleDateFormat("HH:mm");
        
    public int solution(String[][] book_time) {
        
        int[][] bookTimeMin = new int[book_time.length][2];
        
        for(int i =0; i<book_time.length; i++){
            String time1 = book_time[i][0];
            String time2 = book_time[i][1];
            
            try{
            Date date1 = format.parse(time1);
            Date date2 = format.parse(time2);    
            long dToM1 = date1.getTime();
            long dToM2 = date2.getTime();
            int m1 = (int) (dToM1 / MINIUTES_STANDARD);
            int m2 = (int) (dToM2 / MINIUTES_STANDARD);
            
            bookTimeMin[i][0] = m1;
            bookTimeMin[i][1] = m2+10; // 청소시간도 함께 더해준다.
            }
            catch(Exception e){}
        }
        
        // 정렬 시작시간 기준 오름차순
        Arrays.sort(bookTimeMin, (o1,o2) -> {
            if (o1[0] == o2[0]){
                return o1[1]-o2[1];
            }
            else{
                return o1[0]-o2[0];
            }
        });
        
        // 방 예약
        List<Integer> room = new ArrayList<>();
        for(int i =0; i<book_time.length; i++){
            Collections.sort(room); // 방은 항상 오름차순으로 정렬되어야한다.(방의 끝시간 기준으로)
            boolean isBook = false;
            
            for (int j = 0; j < room.size(); j++) { // 할당된 방을 순차적으로 돈다.
				if (bookTimeMin[i][0] >= room.get(j)) { // 만약 방의 끝시간 <= 다음 넣어야할 예약의 첫 시간 인 경우
					room.set(j, bookTimeMin[i][1]); // 기존 방에 추가한다.
					isBook = true; // 예약했음.
					break;
				}
			}
            
            if(!isBook)// 예약 못한경우
            {
                room.add(bookTimeMin[i][1]); // 끝 시간을 방에 넣는다.
            }
        }
        
        int answer = room.size();
        
        return answer;
    }
}