프로그래머스의 호텔 대실 문제를 함께 풀어보도록 하겠습니다.
문제
호텔을 운영 중인 코니는 최소한의 객실만을 사용하여 예약 손님들을 받으려고 합니다. 한 번 사용한 객실은 퇴실 시간을 기준으로 10분간 청소를 하고 다음 손님들이 사용할 수 있습니다. 예약 시각이 문자열 형태로 담긴 2차원 배열 book_time이 매개변수로 주어질 때, 코니에게 필요한 최소 객실의 수를 return 하는 solution 함수를 완성해주세요.
예제
입력: [["15:00", "17:00"], ["16:40", "18:20"], ["14:20", "15:20"], ["14:10", "19:20"], ["18:20", "21:20"]]
출력: 3입력: [["09:10", "10:10"], ["10:20", "12:20"]]
출력: 1입력: [["10:20", "12:30"], ["10:20", "12:30"], ["10:20", "12:30"]]
출력: 3풀이 1: 최소 힙
최소한의 객실만을 사용하여 예약 손님들을 받으려면 하나의 객실에 최대한 많은 손님이 묶어야 할 텐데요. 새로운 손님이 왔을 때, 이전에 다른 손님이 사용한 객실 중에서 입실 가능한 객실을 어떻게 알아낼 수 있을까요? 여태까지 손님이 묶었던 객실 중에서 가장 빨리 입실이 가능한 객실을 찾아야 할 것입니다. 그 객실에 아직 입실할 수 없는 상황이라면 더 늦게 퇴실하는 다른 객실에도 당연히 입실이 불가능할테니까요.
가장 이른 대실 종료 시간이 새로운 손님이 입실해야하는 시간보다 더 이르다면 우리는 해당 객실에 손님을 배정할 수 있습니다. 하지만 가장 이른 대실 종료 시간이 새로운 손님이 입실해야하는 시간보다 더 늦는다면 우리는 그 손님을 위해서 객실이 하나 더 필요하게 됩니다.
즉, 현재 손님 중에서 가장 일찍 퇴실하는 시간과 다음 손님이 입실해야 하는 시간을 비교하면, 새로운 객실이 하나 더 필요한지, 아니면 기존에 다른 손님이 사용했던 객실을 재배정할 수 있는지 판단할 수 있게 됩니다.
- 가장 이른 퇴실 시간 + 10분 <= 다음 손님 입실 시간 👉 기존 객실 배정
- 가장 이른 퇴실 시간 + 10분 > 다음 손님 입실 시간 👉 신규 객실 필요
이런 상황에서는 힙(Heap)이라는 자료구조를 사용하면 딱인데요.
최소 힙(Min Heap)에 여태까지 모든 퇴실 시간을 저장해놓으면 가장 이른 퇴실 시간을 O(1), 즉 상수 시간에 알아낼 수 있기 때문입니다.
기본 아이디어는 주어진 입력 배열을 대실 시작 시간 순으로 오름차순 정렬을 해놓고, 입력 배열을 상대로 루프를 돕니다. 다음 손님의 입실 시간이 가장 이른 퇴실 시간에 10분을 더한 시간보다 이른 경우에는 객실에 하나 더 필요하므로 새로운 손님의 퇴실 시간을 힙에 추가합니다. 반대의 경우에는 가장 일찍 퇴실한 객실에 새로운 손님을 배정할 수 있습니다. 따라서 가장 이른 퇴실 시간을 힙에서 제거하고 새로운 손님의 퇴실 시간을 추가하는 것입니다.
루프가 끝나면 최종적으로 최소 힙에 남아있는 퇴실 시간의 개수가 바로 우리가 찾고자 하는 최소한의 객실의 개수가 될 것입니다.
이 알고리즘을 문제에서 주어진 첫 번째 예제에 적용해볼께요.
________________
["14:10", "19:20"], ["14:20", "15:20"], ["15:00", "17:00"], ["16:40", "18:20"], ["18:20", "21:20"]
👉 첫 번째 손님을 위해서 무조건 신규 객실 필요
push "19:20" + "00:10"
최소 힙: ["19:30"] ________________
["14:10", "19:20"], ["14:20", "15:20"], ["15:00", "17:00"], ["16:40", "18:20"], ["18:20", "21:20"]
- 가장 이른 퇴실 시간: "19:20"
- 다음 손님 입실 시간: "14:20"
"19:30" > "14:20" 👉 신규 객실 필요
push "15:20" + "00:10"
최소 힙: ["15:30", "19:30"] ________________
["14:10", "19:20"], ["14:20", "15:20"], ["15:00", "17:00"], ["16:40", "18:20"], ["18:20", "21:20"]
- 가장 이른 퇴실 시간: "15:20"
- 다음 손님 입실 시간: "15:00"
"15:30" > "15:00" 👉 신규 객실 필요
push "17:00" + "00:10"
최소 힙: ["15:30", "17:10", "19:30"] ________________
["14:10", "19:20"], ["14:20", "15:20"], ["15:00", "17:00"], ["16:40", "18:20"], ["18:20", "21:20"]
- 가장 이른 퇴실 시간: "15:20"
- 다음 손님 입실 시간: "16:40"
"15:30" < "16:40" 👉 기존 객실 배정
pop "15:30"
push "18:20" + "00:10"
최소 힙: ["17:10", "18:30", "19:30"] ________________
["14:10", "19:20"], ["14:20", "15:20"], ["15:00", "17:00"], ["16:40", "18:20"], ["18:20", "21:20"]
- 가장 이른 퇴실 시간: "17:00"
- 다음 손님 입실 시간: "18:20
"17:10" < "18:20" 👉 기존 객실 배정
pop "17:10"
push "21:20" + "00:10"
최소 힙: ["18:30", "19:30", "21:30"]그럼 이 알고리즘을 파이썬으로 구현해볼까요?
from heapq import heappush, heappop
def solution(book_time):
book_time.sort()
ends = []
for start, end in book_time:
if ends and ends[0] <= 60 * int(start[:2]) + int(start[3:]):
heappop(ends)
heappush(ends, 60 * int(end[:2]) + int(end[3:]) + 10)
return len(ends)입력 배열의 크기를 n이라고 했을 때, 이 풀이의 시간 복잡도는 O(nlog(n))이 되는데요.
정렬에 O(nlog(n)) 시간이 소요되고, O(log n), 즉 로그 시간이 소요되는 힙에 데이터 추가나 삭제하는 작업을 n번 반복하기 때문입니다.
반면에 공간 복잡도는 최악의 경우 힙의 크기가 n이 될 수 있어서 O(n)입니다.
풀이 2: 따로 정렬
입력 배열을 시작 시간으로 정렬하면 새로운 객실이 언제 필요한지는 순서대로 알 수 있지만, 기존에 쓰던 객실이 언제 비는지는 그 순서를 알 수가 없는데요. 만약에 대실 시작 시간과 대실 종료 시간을 따로 정렬하면 어떨까요? 그러면 객실이 언제 다음 손님을 위해 준비되는지도 순서대로 알 수 있겠죠?
예를 들어, 첫 번째 예제에서 주어진 입력 배열을 시작 시간과 종료 시간으로 분리하여 정렬해보겠습니다.
입력 배열: ["14:10", "19:20"], ["14:20", "15:20"], ["15:00", "17:00"], ["16:40", "18:20"], ["18:20", "21:20"]
시작 시간: ["14:10", "14:20", "15:00", "16:40", "18:20"]
종료 시간: ["15:20", "17:00", "18:20", "19:20", "21:20"]그리고 시작 포인터가 가리키는 시간과 종료 포인터가 가리키는 시간을 비교하면서 2개의 배열을 동시에 탐색하면, 추가 객실이 필요한 시점과 기존 객실이 비는 시점을 찾을 수 있을 것입니다.
_______
시작 시간: ["14:10", "14:20", "15:00", "16:40", "18:20"]
_______
종료 시간: ["15:20", "17:00", "18:20", "19:20", "21:20"]
"14:10" < "15:20" + "00:10" 👉 신규 객실 필요
필요한 객실: 1 _______
시작 시간: ["14:10", "14:20", "15:00", "16:40", "18:20"]
_______
종료 시간: ["15:20", "17:00", "18:20", "19:20", "21:20"]
"14:20" < "15:20" + "00:10" 👉 신규 객실 필요
필요한 객실: 2 _______
시작 시간: ["14:10", "14:20", "15:00", "16:40", "18:20"]
_______
종료 시간: ["15:20", "17:00", "18:20", "19:20", "21:20"]
"15:00" < "15:20" + "00:10" 👉 신규 객실 필요
필요한 객실: 3 _______
시작 시간: ["14:10", "14:20", "15:00", "16:40", "18:20"]
_______
종료 시간: ["15:20", "17:00", "18:20", "19:20", "21:20"]
"16:40" > "15:20" + "00:10" 👉 기존 객실 배정
필요한 객실: 2 _______
시작 시간: ["14:10", "14:20", "15:00", "16:40", "18:20"]
_______
종료 시간: ["15:20", "17:00", "18:20", "19:20", "21:20"]
"16:40" < "17:00" + "00:10" 👉 신규 객실 필요
필요한 객실: 3 _______
시작 시간: ["14:10", "14:20", "15:00", "16:40", "18:20"]
_______
종료 시간: ["15:20", "17:00", "18:20", "19:20", "21:20"]
"18:20" > "17:00" + "00:10" 👉 기존 객실 배정
필요한 객실: 2이런 식으로 시작 포인터가 배열의 끝에 도달하면 모든 시작 시간을 고려하게 되었으며 남은 종료 시간은 굳이 고려할 필요가 없습니다. 우리가 구해야하는 것은 객실이 가장 많이 필요할 때의 객실의 개수이고, 남은 종료 시간은 오직 필요한 객실의 개수를 감소시키기만 할테니까요.
그럼 이 알고리즘을 파이썬으로 구현해보겠습니다.
def solution(book_time):
starts = sorted(60 * int(s[:2]) + int(s[3:]) for s, _ in book_time)
ends = sorted(60 * int(e[:2]) + int(e[3:]) for _, e in book_time)
max_cnt, cnt = 0, 0
s, e = 0, 0
while s < len(starts):
if ends[e] + 10 <= starts[s]:
cnt, e = cnt - 1, e + 1
else:
cnt, s = cnt + 1, s + 1
max_cnt = max(cnt, max_cnt)
return max_cnt동일한 코드를 자바스크립트로 구현하면 다음과 같습니다.
function solution(book_time) {
const starts = book_time
.map(([s, _]) => 60 * parseInt(s.slice(0, 2)) + parseInt(s.slice(3)))
.sort((a, b) => a - b);
const ends = book_time
.map(([_, e]) => 60 * parseInt(e.slice(0, 2)) + parseInt(e.slice(3)))
.sort((a, b) => a - b);
let max_cnt = 0,
cnt = 0;
let s = 0,
e = 0;
while (s < starts.length) {
if (ends[e] + 10 <= starts[s]) {
cnt--;
e++;
} else {
cnt++;
s++;
max_cnt = Math.max(cnt, max_cnt);
}
}
return max_cnt;
}입력 배열의 크기를 n이라고 했을 때, 이 풀이의 시간 복잡도는 O(nlog(n))이 되는데요.
O(nlog(n)) 시간이 걸리는 정렬을 두 번 수행한 후에, 2n만큼의 반복을 하고 있기 때문입니다.
즉, 빅오 계산법에 따라서 O(2nlog(n) + 2n) = O(nlog(n))이 성립하게 됩니다.
반면에 공간 복잡도는 두 개의 추가 배열이 2n의 추가 공간을 사용하므로 O(n)이 되겠습니다.
풀이 3: 같이 정렬
모든 객실의 대실이 언제 시작하고 언제 끝나는지를 하나의 시간 선상에서 순서대로 표시해보면 어떨까요? 예를 들어, 첫 번째 예제에서 주어진 객실들이 시간이 지남에 따라서 언제 입실하고 언제 퇴실하는지를 시각화해보겠습니다.
입력 배열: ["15:00", "17:00"], ["16:40", "18:20"], ["14:20", "15:20"], ["14:10", "19:20"], ["18:20", "21:20"]
"14:10": ["14:10", "19:20"] 입실 👉 객실 1개 필요 (+1)
"14:20": ["14:20", "15:20"] 입실 👉 객실 2개 필요 (+1)
"15:00": ["15:00", "17:00"] 입실 👉 객실 3개 필요 (+1)
"15:30": ["14:20", "15:20"] 퇴실 👉 객실 2개 필요 (-1)
"16:40": ["16:40", "18:20"] 입실 👉 객실 3개 필요 (+1)
"17:10": ["15:00", "17:00"] 퇴실 👉 객실 2개 필요 (-1)
"18:20": ["18:20", "21:20"] 입실 👉 객실 3개 필요 (+1)
"18:30": ["16:40", "18:20"] 퇴실 👉 객실 2개 필요 (-1)
"19:30": ["14:10", "19:20"] 퇴실 👉 객실 1개 필요 (-1)
"21:30": ["18:20", "21:20"] 퇴실 👉 객실 0개 필요 (-1)보시다시피 입실 때 때 마다 새로운 객실이 필요하고, 퇴실 때 마다 객실 하나가 필요 없어집니다.
따라서 대실 시작 시간과 대실 종료 시간을 함께 묶어서 오름차순 정렬한다면 이 문제를 간단하게 해결할 수 있을 것입니다.
시작 시간에는 객실이 하나 더 필요하기 때문에 +1을 덧붙이고, 종료 시간에는 객실이 하나 덜 필요하기 때문에 -1을 덧붙이겠습니다.
[("14:10", +1), ("14:20", +1), ("15:00", +1), ("15:30", -1), ("16:40", -1), ("17:10", -1), ("18:20", +1), ("18:30", -1), ("19:30", -1), ("21:30", -1)]자, 이제 시작 시간과 종료 시간이 통합된 배열을 루프 돌면서 덧붙인 +1 또는 -1을 모두 더해주기만 하면 되겠죠?
그럼 이 알고리즘을 파이썬으로 구현해볼까요?
def solution(book_time):
pairs = []
for start, end in book_time:
pairs.append((60 * int(start[:2]) + int(start[3:]), 1))
pairs.append((60 * int(end[:2]) + int(end[3:]) + 10, -1))
pairs.sort()
max_cnt, cnt = 0, 0
for _, delta in pairs:
cnt += delta
max_cnt = max(cnt, max_cnt)
return max_cnt동일한 코드를 자바스크립트로 구현하면 다음과 같습니다.
function solution(book_time) {
const pairs = [];
for (const [start, end] of book_time) {
pairs.push([
60 * parseInt(start.slice(0, 2)) + parseInt(start.slice(3)),
1,
]);
pairs.push([
60 * parseInt(end.slice(0, 2)) + parseInt(end.slice(3)) + 10,
-1,
]);
}
pairs.sort((a, b) => {
if (a[0] === b[0]) return a[1] - b[1];
return a[0] - b[0];
});
let max_cnt = 0;
let cnt = 0;
for (const [, delta] of pairs) {
cnt += delta;
max_cnt = Math.max(cnt, max_cnt);
}
return max_cnt;
}입력 배열의 크기를 n이라고 했을 때, 이 풀이의 시간 복잡도는 O(nlog(n))입니다.
크기가 2n인 통합 배열을 정렬하는데 O(2nlog(2n))의 걸리는데 빅오 계산법으로 O(nlog(n))이 되기 때문입니다.
반면에 공간 복잡도는 통합 배열이 2n의 추가 공간을 필요로 하므로 O(n)이 되겠습니다.
마치면서
3가지 풀이 방법 모두 어느 정도 직관(intuition)을 요하는 쉽지 않은 문제였는데요. 이러한 직관은 코딩 문제를 많이 푸시다보시면 자연스럽게 길러지므로 한 번에 이해가 되지 않으시더라도 좌절하시지 않으셨으면 좋겠습니다. 복잡도는 동일하기 때문에 이 중에서 한 가지 방법으로만 풀 수 있으시다면 큰 지장은 없을 것입니다.
코딩 테스트에서 구간을 어떻게 다루는지에 대해서 더 공부하고 싶으시다면 관련 게시물을 참고 바랄께요.