[Algorithm] Programmers_호텔 대실 in Java

💡 Programmers Lv2. 호텔 대실:

효율적으로 방 예약하기

🌱 코드 in Java

알고리즘: Priority Queue

import java.util.*;

class Solution {
    public int solution(String[][] book_time) {
        Arrays.sort(book_time, (x, y) -> x[0].compareTo(y[0])); // 스트링 배열 시작 시간 기준 정렬
        PriorityQueue<int[]> room = new PriorityQueue<>((x, y) -> x[1] - y[1]); // 끝나는 시간을 기준으로 하는 우선순위 큐 객체 생성
        
        for (String[] book : book_time) { // 정렬된 예약 순회
            String[] start = book[0].split(":"); // ":" 기준 split
            String[] end = book[1].split(":");
            
            int s_time = Integer.parseInt(start[0]) * 60 + Integer.parseInt(start[1]); // 비교를 위한 int 변환
            int e_time = Integer.parseInt(end[0]) * 60 + Integer.parseInt(end[1]) + 10; // 청소 시간 10분 더하기
            
            if (!room.isEmpty() && room.peek()[1] <= s_time) // 큐, 즉 사용 중인 방이 있을 경우 가장 빨리 끝나는 방의 시간과 현재 예약 시작 시간을 비교하여 사용이 가능할 경우
                room.poll(); // 큐에서 제거
            room.add(new int[]{s_time, e_time}); // 큐에 현재 예약건 삽입
        }
        return room.size(); // 큐의 길이가 곧 최소 방의 갯수
    }
}

이번 문제에서 어려웠던 것은 일단 자바의 split 함수를 몰랐고, 처음에 우선순위큐를 떠올리지 못해 아래와 같이 Map을 사용하여 풀었었다.

class Solution {
    public int solution(String[][] book_time) {
        int j;
        Arrays.sort(book_time, (x, y) -> x[0].compareTo(y[0]));
        Map<Integer, Integer> room = new HashMap<>();
        
		for (int i = 0; i < book_time.length; i++) {
            String[] start = book_time[i][0].split(":");
            String[] end = book_time[i][1].split(":");
            
            int s_time = Integer.parseInt(start[0]) * 60 + Integer.parseInt(start[1]);
            int e_time = Integer.parseInt(end[0]) * 60 + Integer.parseInt(end[1]) + 10;
            
            for (j = 1; j <= room.size(); j++) { // 이렇게 맵을 다 뒤지지 않도록 우선순위큐를 사용했어야 했다.
                if (room.get(j) <= s_time)
                    break;
            }
            room.put(j, e_time);
        }
        return room.size();
    }
}

for (j = 1; j <= room.size(); j++) 이 부분이 맵을 사용함으로써 나타난 불필요한 반복문이었다.
우선순위큐 사용 시 가장 빨리 끝나는 방이 항상 맨 앞에 있기 때문에 peek를 통해서 간단히 비교할 수 있는 반면, 맵을 사용하니 해당 맵을 전체를 순회해야하는 문제가 발생했다. 왜 우선순위큐를 떠올리지 못했는지 나참.

아무튼 중요한 것은 어차피 새로운 예약건을 확인할 경우 사용할 수 없는 방이 없건, 사용이 끝난 방을 재사용하건 결국은 새로운 예약건으로 방의 정보를 갱신해주어야 한다는 것이다. 따라서 room.add() 부분은 어떤 경우에도 발생하는 로직이다.사용 중이던 방이 있을 경우 시간 비교 후 제거해야 한다면 제거하고 현재 방을 다시 큐에 넣어주면 된다.

🧠 기억하자

1. PriorityQueue
   아래와 같이 선언할 수 있다.

• PriorityQueue<Integer> pq = new PriorityQueue<>()
• PriorityQueue<Integer> p1 = new PriorityQueue<>(Collections.reverseOrder());

또한, 위의 코드에서 사용한 것처럼 람다식 함수를 사용하여 compare 메서드를 구현하여 어떤 식으로 비교할 것인지 정해줄 수 있다.

람다식 표현을 정말 빨리 공부해야겠다.. 쥬륵..

우선순위큐는 add, poll, peek과 같은 함수를 사용한다.

2. String.split("구분자")

• String[] parts = originalText.split("구분자");
  와 같은 형태로 사용이 가능하다. 구분자로 기본 문장을 나누어 배열에 넣어준다.