[프로그래머스] 호텔 대실 / 자바(Java)

• 문제

• 해설

• 최종 코드

• 추가코드

문제

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

프로그래머스

 

---

해설

예약시간이 주어질 때 시간이 겹치지 않기 위한 최소한의 방의 개수를 구하는 문제이다.

만약 Bruteforce로 해결하려 한다면 배열 book_time의 길이가 1000이므로 1000!이 되어 연산이 불가능할 정도로 커진다.

 

따라서 그리디방식을 사용하여 문제를 풀기로 했다.

(1)시작시간을 기준으로 정렬해주어 시간순서대로 방에 들어가도록 해주고, (2)새로운 시간이 들어올 때마다 끝나는 순서로 정렬해주어 가장 빨리 비는 방에 다시 들어가도록 한다면 각 방을 빡빡하게 사용할 수 있어 최소한의 방을 사용했다고 보장가능하다. 

1. 시작시간을 기준으로 정렬

book_time[i]의 두 값을 하나로 묶은 상태의 정렬값이 필요해 객체를 만들어 정렬된 리스트를 가지도록 하였습니다. 

Collections.sort를 사용하면 시간복잡도가 O(NlogN)이 되어 입력값이 1000인 문제에서 부담없이 사용하였습니다.

// 정렬을 위한 객체
public class Reservation implements Comparable<Reservation>{
        int start_time;
        int end_time;
        
        public Reservation(int start_time, int end_time){
            this.start_time = start_time;
            this.end_time = end_time;
        }
        @Override
        public int compareTo(Reservation o) {
            return this.start_time-o.start_time==0 ? this.end_time - o.end_time : this.start_time-o.start_time;
        }
}
    
 // 정렬
    
public int solution(String[][] book_time) {
    	int answer = 0;
   	 List<Reservation> l = new ArrayList<>();
    	for(String[] cur : book_time){
        	l.add(inputToReservation(cur));
    	}
        
    	Collections.sort(l);
        
   	 return answer;
}

// 객체리스트의 생성을 쉽게하기위해 입력을 객체로 변환하는 함수

public Reservation inputToReservation(String[] input){
        String[] start = input[0].split(":");
        String[] end = input[1].split(":");
        
        int start_time = Integer.parseInt(start[1])+Integer.parseInt(start[0]) * 60;
        int end_time = Integer.parseInt(end[1])+Integer.parseInt(end[0]) * 60 + 10;
        return new Reservation(start_time, end_time);
}

 

2. 새로운 시간이 들어올 때 마다 끝나는 순서로 정렬 및 빈 방에 넣기

이번 문제의 중요한 부분입니다. 

값을 넣을 때 마다 정렬이되는 우선순위큐를 사용해 그 안에 각 시간의 종료시간을 넣도록 합니다. 

만약 우선순위큐가 비어있거나(처음 방에 들어가는 상황), 가장 빠른 종료시간이 시작시간보다 크거나 같다면(어느 방이든 사용중인 경우) 새로 방을 내어주어야 하기때문에 방의 최대값(answer)를 증가시켜주고 그 외의 경우(방의 사용이 끝난 경우)는 그 방에 다시 들어가기만 하면 되기 때문에 해당 예약 내용을 빼어주고 다시 그 방을 사용한다는 개념이므로 방의 최대값에 영향이 없습니다.

	PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(Reservation r : l){
            if(!pq.isEmpty() && pq.peek()<=r.start_time){
                pq.poll();
            }else{
                answer++;
            }
            pq.add(r.end_time);
        }

 

---

최종 코드

import java.util.*;
class Solution {
    
    public class Reservation implements Comparable<Reservation>{
        int start_time;
        int end_time;
        
        public Reservation(int start_time, int end_time){
            this.start_time = start_time;
            this.end_time = end_time;
        }
        @Override
        public int compareTo(Reservation o) {
            return this.start_time-o.start_time==0 ? this.end_time - o.end_time : this.start_time-o.start_time;
        }
    }
    
    public int solution(String[][] book_time) {
        int answer = 0;
        List<Reservation> l = new ArrayList<>();
        for(String[] cur : book_time){
            l.add(inputToReservation(cur));
        }
        
        Collections.sort(l);
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(Reservation r : l){
            if(!pq.isEmpty() && pq.peek()<=r.start_time){
                pq.poll();
            }else{
                answer++;
            }
            pq.add(r.end_time);
        }
        
        return answer;
    }
    
    public Reservation inputToReservation(String[] input){
        String[] start = input[0].split(":");
        String[] end = input[1].split(":");
        
        int start_time = Integer.parseInt(start[1])+Integer.parseInt(start[0]) * 60;
        int end_time = Integer.parseInt(end[1])+Integer.parseInt(end[0]) * 60 + 10;
        return new Reservation(start_time, end_time);
    }
}

 

추가코드

객체를 생성 및 리스트로 정렬하는 것이 아닌 2차원 배열에서 바로 람다식을 통해 정렬하는 코드입니다. 

기본적인 아이디어는 같지만 공간 복잡도 및 코드를 생성하는데 더 간편한 면이 있어 추가로 가져왔습니다.

import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int solution(String[][] book_time) {

        int[][] bkt = new int[book_time.length][];

        for (int i = 0; i < book_time.length; i++) {
            bkt[i] = new int[] { parseTime(book_time[i][0]), parseTime(book_time[i][1]) + 10 };
        }

        Arrays.sort(bkt, (a, b) -> a[0] - b[0]);

        PriorityQueue<int[]> que = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        int ans = 0;

        for (int i = 0; i < bkt.length; i++) {
            while (!que.isEmpty() && que.peek()[1] <= bkt[i][0]) {
                que.poll();
            }
            que.add(bkt[i]);
            ans = Math.max(ans, que.size());
        }

        return ans;
    }

    protected int parseTime(String time) {

        String[] hhmm = time.split(":");
        int hour = Integer.parseInt(hhmm[0]), min = Integer.parseInt(hhmm[1]);
        return hour * 60 + min;

    }
}