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

안녕하세요.

 

이번엔 프로그래머스 lv2 155651 호텔 대실 문제를 파이썬으로 풀어보겠습니다.

문제 링크는 여기입니다.

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

프로그래머스

---

풀이

 

효율적인 계산을 하려면 누적합 방식을 사용하는 것이 좋아보입니다.

누적합이란, 어떠한 배열 N이 있을 때,

새로운 배열 sum에 합을 누적시켜 저장하는 것입니다.

예를 들어 N = [ 1, 3, 2, 5, 1 ] 이라고 하면,

누적합을 저장할 리스트 sum을 만들어서, [ 1, 4(1+3의 결과), 6(4 + 2), 11, 12] 이런식으로 저장하는 것입니다.

자세한 설명으로는 이 글이 좋겠습니다.

https://jow1025.tistory.com/47

누적합(prefix sum)

 

그래서 누적합 얘기가 왜 나왔냐하면,

분 단위로 쪼갠 타임테이블을 리스트로 생성하고,

겹치는 시간 파악을 위해서

각 시간별 체크인 시간에 1을 더하고, 체크아웃 시간에 1을 빼는 방식으로 타임테이블을 생성합니다.

그러면 체크인시간과 체크아웃 시간 사이(대실 시간)를 제외한 시간은 누적합의 영향을 받지 않고, (체크인에서 더하고 체크아웃에서 그만큼 빼니까요)

겹친 시간대는 누적합이 가장 클 것입니다.

무슨 소리인지 잘 모르겠으면 예시를 한 번 보면서 곰곰이 생각해보세요.

 

예를 들어볼까요.

 

문제 상세조건을 잠깐 떠나서 예시를 들면,

10시~11시 가 있고 10시반~11시반이 있고 9시~9시반 이라는 예약이 있다고 합시다.

머릿속으로 생각해보면 방이 두 개가 필요할 것입니다.

 

10시는 체크인이니까 배열에서 10시 위치에 +1

11시는 체크아웃이니까 배열에서 11시 위치에 -1

...

9시는 체크인시간이니까 배열에서 9시 위치에 +1

9시반은 체크아웃시간이니까 9시30분 위치에 -1

배열로는 이렇게 되겠죠?

 

	09:00	09:30	10:00	10:30	11:00	11:30	12:00
배열	1	-1	1	1	-1	-1	0

 

이런식으로 진행해서 누적합을 구하면

 

	09:00	09:30	10:00	10:30	11:00	11:30	12:00
누적합	1	0	1	2	1	0	0

 

10:30에 누적합이 2, 즉 2개의 예약이 있다 라는 결론을 얻어낼 수 있습니다. 결국 방이 두 개가 필요하단 걸 알 수 있죠.

이를 이해하셨다면, 사실 코드로 구현하는 과정은 어렵지 않습니다.

 

코드로 보면 다음과 같습니다.

def minute(t):
    [h, m] = t.split(':')
    return int(h) * 60 + int(m)

def solution(book_time):
    answer = 0
    rooms = [0 for _ in range(24*60 + 10)]
    for i in book_time: 
        ci = minute(i[0])
        co = minute(i[1]) + 10
        rooms[ci] += 1
        rooms[co] -= 1
    #누적합  
    for i in range(1, len(rooms)):
        rooms[i] += rooms[i - 1]
    answer = max(rooms)
    return answer

 

감사합니다.