프로그래머스 호텔 대실 155651 Python

프로그래머스 호텔 대실 155651 python

---

문제

문제

여러 예약 구간이 [시작, 종료] 형태로 주어집니다. 한 번 사용한 객실은 **퇴실 뒤 10분 청소**가 끝난 다음에야 다시 사용할 수 있습니다. 모든 예약을 처리하기 위해 필요한 **최소 객실 수**를 구하는 문제입니다.

테스트케이스

1. [["15:00","17:00"],["16:40","18:20"],["14:20","15:20"],["14:10","19:20"],["18:20","21:20"]] → 3
2. [["09:10","10:10"],["10:20","12:20"]] → 1
3. [["10:20","12:30"],["10:20","12:30"],["10:20","12:30"]] → 3

문제 작동원리

시간축 위에서 **동시에 진행 중인 예약의 개수**가 어느 순간 최대 \(K\)라면, 그 순간에는 객실이 최소 \(K\)개 필요합니다. 또한 퇴실 후 **10분 청소** 때문에, 내부적으로는 **종료시각 + 10분**을 “점유 끝”으로 취급해야 합니다.
결국 **시간이 흐르면서**

• 누군가 **입실**하면 “현재 사용 객실 수”를 \(+1\),
• 누군가 **퇴실+청소 완료**되면 “현재 사용 객실 수”를 \(-1\)로 갱신했을 때,

그 **최대값**이 곧 **필요한 최소 객실 수**입니다.

---

아이디어

아래 모든 시각화에서는 **퇴실 뒤 10분**이 자동 반영되도록, 막대의 오른쪽 끝(퇴실 시각)을 **+10분** 늘려서 그립니다. 이렇게 해야 “붙여쓰기 가능한가?”가 정확히 반영됩니다.

1) 겹치지 않는 경우(완전히 비껴감)

시간 ───────────────────────────────────▶
A: [09:00───────────────────10:00) ─ 청소 → 점유 종료 10:10
B:                                 [10:20───────────11:00) ─ 청소 → 점유 종료 11:10

• 09:00~10:10: A만 점유 → 현재 사용 객실 1
• 10:10~10:20: 아무도 없음 → 0
• 10:20~11:10: B만 점유 → 1

**최대값 = 1** → 객실 1개로 충분합니다.
포인트: 종료+10(10:10)과 다음 시작(10:20) 사이에 **10분 이상 여유**가 있어 자연스럽게 한 객실로 순환됩니다.

2) 끝과 시작이 “딱 맞닿는” 경우(경계 접촉)

시간 ───────────────────────────────────▶
A: [09:00─────────────10:00) ─ 청소 → 점유 종료 10:10
B:                          [10:10────────────11:00) ─ 청소 → 점유 종료 11:10

• 09:00~10:10: A만 → 1
• 10:10 순간: A가 **청소까지 끝**남과 동시에 B가 **시작**

이때 **끝을 먼저 처리**하고(\(-1\)) 바로 **시작을 처리**(\(+1\))하면, 현재 사용 객실 수가 계속 1로 유지됩니다.

• 10:10~11:10: B만 → 1

**최대값 = 1** → 객실 1개.
포인트: **청소를 끝에 미리 더했기 때문에**, “시작과 점유 종료가 같은 시각”이면 같은 방 **재사용 가능**입니다.

3) 일부만 겹치는 경우(반 겹침, 부분 겹침)

시간 ───────────────────────────────────▶
A: [09:00───────────────────10:00) ─ 청소 → 점유 종료 10:10
B:                    [09:50───────────────10:30) ─ 청소 → 점유 종료 10:40

• 09:00~09:50: A만 → 1
• 09:50~10:10: A와 B가 **겹침** → 2
• 10:10~10:40: A는 끝났고(청소 포함), B만 → 1

**최대값 = 2** → 객실 2개 필요.
포인트: “퇴실+청소(10:10)” 이전에는 같은 방 재사용 불가이므로 겹치는 20분(09:50~10:10) 동안은 **두 객실**이 필요합니다.

4) 세 구간이 무겁게 겹치는 경우

원래 예시(청소 반영 후):

시간 ───────────────────────────────────────────────────▶
A: [09:00───────────────────10:00) → 점유 종료 10:10
B:             [09:30─────────────────────10:30) → 점유 종료 10:40
C:                                              [10:30───────────11:00) → 점유 종료 11:10
D:                                  [10:15───────────10:45) → 점유 종료 10:55
(※ 오른쪽 끝은 모두 +10분 반영한 “점유 종료” 시각입니다.)

구간별 동시 점유 개수:

• 09:00~09:30: A → 1
• 09:30~10:10: A, B → 2
• 10:10~10:15: B → 1
• 10:15~10:30: **B, D** → 2
• **10:30~10:40: B, C, D** → **3**
• 10:40~10:55: C, D → 2
• 10:55~11:10: C → 1

**최대값 = 3** → 객실 최소 3개.
포인트: 청소 10분 때문에 C(10:30 시작)는 B(10:40 점유 종료)와 10분 **겹치고**, 동시에 D(10:55 점유 종료)도 살아 있어 **3개**가 필요해집니다.

5) 전부 같은 시간대인 경우(가장 빡빡)

시간 ───────────────────────────────────▶
A: [10:20──────────────────────────12:30) → 점유 종료 12:40
B: [10:20──────────────────────────12:30) → 점유 종료 12:40
C: [10:20──────────────────────────12:30) → 점유 종료 12:40

• 10:20~12:40 내내 세 구간이 겹침 → **최대값 3** → 객실 3개.

요약 아이디어: **막대(예약)의 오른쪽 끝을 10분 밀어 놓고** 시간축에서 “동시에 켜져 있는 막대 수”의 **최댓값**을 찾으면, 그 값이 그대로 **최소 객실 수**입니다.
동시 시각에는 **끝(점유 종료)을 먼저 처리**한 뒤 시작을 처리하면 재사용이 정확히 반영됩니다.

---

전체코드

내가 올린 코드(동작 원리: 시작·종료 시각을 정렬해 두 포인터로 훑으며 “현재 점유 객실 수”의 최댓값을 구함. 종료에는 **청소 10분**을 미리 더해 둡니다.)

def solution(book_time):
    book_time = [[int(h)*60 + int(m) for h,m in (t.split(":") for t in pair)] for pair in book_time]
    s = [i for i,j in book_time]
    e = [j+10 for i,j in book_time]
    s.sort()
    e.sort()
    i = 0
    j = 0
    cnt = 0
    max_cnt = 0
    N = len(book_time)
    while i < N and j < N:
        if s[i] < e[j]:
            cnt += 1
            i += 1
            if(max_cnt < cnt):
                max_cnt = cnt
        else:
            cnt -= 1
            j += 1
    answer = max_cnt
    return answer

핵심 비교가 s[i] < e[j]인 이유:
종료에 청소 10분을 더해두었으므로, **시작이 종료와 같다면**(= 청소가 막 끝난 시각) **재사용 가능**입니다. 따라서 동률에서는 종료를 먼저 처리(\(-1\))하고, 그다음 시작(\(+1\))을 처리해야 합니다. 이 의미가 코드에서는 < 비교로 구현되어 있습니다.

---

결론

• 이 문제는 “모든 예약을 처리할 때 **동시에 필요한 객실 수**의 최댓값 = **최소 객실 수**”라는 간단한 원리로 해결됩니다.
• 단, **퇴실 후 10분 청소**를 반드시 반영해야 하므로, 내부적으로는 “종료시각 + 10분”을 **점유 종료 시각**으로 취급해야 정확합니다.
• 시각화를 통해 막대를 겹쳐 보면 답이 자연스럽게 보이며, 코드에서는 시작과 점유 종료를 시간순으로 훑으면서 “현재 사용 중”의 최댓값을 구하면 됩니다.
• 위 코드로 세 예시(3, 1, 3)가 모두 정확히 계산됩니다.