호텔 대실 (자바, Java)

 

처음엔 백준에서 풀던 문제와 비슷해서, 그리디인가? 생각을 했습니다.

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

그리디가 맞긴 맞는데...조금 문제가 달랐어요.

위 백준 문제는 회의실 하나로 최대한의 회의를 잡기,

해당 프로그래머스 문제는, 모든 회의를 잡는 최소한의 회의실 수를 구하기.

 

처음에 생각했던 발상은, 백준 문제풀이때의 감각대로

정렬한 뒤 priorityqueue를 활용해 정답을 구하는 쪽이었는데, 접근법은 맞았으나 최종코드를 작성하지 못했습니다.

priorityqueue로 어떻게 구분해서 max값을 구하는지? 이 부분에 대한 이해가 부족했어요.

 

잘 모르겠어서. chatGPT의 도움을 청했습니다.

일단 회의가 시작되면(회의시작값으로 오름차순 정렬한 배열로 반복문), 회의실을 잡아야하므로 큐에 넣어야 합니다.

회의가 시작되기 전에, 회의가 이미 끝난 회의실이 존재한다면 (회의 종료값으로 오름차순 정렬한 우선순위큐), 회의를 큐에서 제거하여, 회의실을 재사용할 수 있게 합니다.

이런 과정을 거쳐, 남아있는 큐의 수 = 필요한 최소한의 회의실 수가 됩니다.

 

이해는 했는데, 비슷한 문제에서 발상을 떠올릴 수 있을지, 자신이 좀 없었습니다.

 

정답 코드

import java.util.*;

class Solution {
    
    final int maxTime = 1450;
    final int hour = 60;
    final int clean = 10;
    
    public int solution(String[][] book_time) {
        int time[][] = new int[book_time.length][2];
        int cnt = 0;
        
        for (int i=0; i<time.length; i++) {
            for (int j=0; j<time[0].length; j++) {
                String[] str = book_time[i][j].split(":");
                time[i][j] = Integer.parseInt(str[0]) * hour + Integer.parseInt(str[1]);
                if (j==1) {
                    time[i][j]+=clean;
                }
            }
        }
        
        Arrays.sort(time, (o1, o2) -> {
            return o1[0]-o2[0];
        });
        
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
        
        for (int[] t : time) {
            if (!pq.isEmpty() && t[0]>=pq.peek()[1]) {
                pq.poll();
            }
            pq.add(t);
        }
        
        return pq.size();
    }
}

 

해당 풀이의 결과값입니다.

 

 

두번째 풀이, 누적합.

누적합은 배운 바도 있었고, 푸는 중간에 누적합으로 접근하는 방법도 고려했었습니다.

다만 분 단위로 쪼개면, 너무 배열의 크기가 커지는 것 아닌가? 하는 걱정이 있었죠.

개인적으로 후회되는 부분은, 효율이 어쨌건 구현하지 못했는데, 일단 구현할 수 있을법한 아이디어에 실행하지 않고

일찍 포기해버린 것. 일단 시도해보는 것이 어땠을까 하는 아쉬움이 남습니다.

 

정답 코드

class Solution {
    
    final int maxTime = 1450;
    final int hour = 60;
    final int clean = 10;
    
    public int solution(String[][] book_time) {
        int answer = 0;
        int time[][] = new int[book_time.length][2];
        int[] sum = new int[maxTime+1];
        int cnt = 0;
        
        for (int i=0; i<time.length; i++) {
            for (int j=0; j<time[0].length; j++) {
                String[] str = book_time[i][j].split(":");
                time[i][j] = Integer.parseInt(str[0]) * hour + Integer.parseInt(str[1]);
                if (j==1) {
                    time[i][j]+=clean;
                    sum[time[i][j]]-=1;
                } else sum[time[i][j]]+=1;
            }
        }
        
        for (int i : sum) {
            cnt+=i;
            answer = Math.max(answer, cnt);
        }
        
        return answer;
    }
}

 

해당 풀이의 결과값입니다.

 

결과적으로 누적합이 훨씬 효율적이었는데,

처음에는 시간을 분 단위로 쪼개 오버헤드 등 메모리 비효율을 걱정했으나,

시간값은 24시간 (+ 청소 10분) 으로 1450분이 고정이라는 점이 유효하지 않았나 싶습니다.

또한, 별도의 정렬이 필요없었다는 점도 큰 요소로 작용했습니다.

 

간만에, 다양한 풀이법으로 접근한 문제였네요.