프로그래머스 호텔 대실

문제 : 호텔 대실

문제 유형 : heap 사용
https://school.programmers.co.kr/learn/courses/30/lessons/155651

프로그래머스

1. 문제 풀이
이번 주차에 1번 문제였던 과제 진행하기와 비슷하게 문자로 된 시간을 숫자로 바꾸는 것이었다. 과제 진행하기 문제에서는 그 부분을 어떻게 할 지 몰라서 한참 헤맸는데 그 때의 경험으로 문자열을 숫자로 바꾸어 주었다.  그 후 시작 시간 기준으로 빠른 순서대로 정렬 해주었다. 

그리고 문제 해법은 과제 진행하기를 참고 했다
먼저 들어온 첫 번째 사람은 Room 1 에 들어간다고 가정하고 

두 번째 사람의 들어온 시간을 첫 번째 사람의 끝나는 시간과 비교 했다.

즉, 첫 번째 사람이 있을 때(첫 번째 사람의 끝나는 시간 > 두 번째 사람의 시작 시간)는 두 번째 사람을 Room 2로 배정하고 그렇지 않을 땐 첫 번째 사람이 없는 것이니 두 번째 사람을 Room 1에 배정해준다. 

처음에는 start_time 과 end_time 모두 넣어줬는데 생각해보니 Room에 사람이 있는 지 비교 할 땐 들어간 사람의 끝나는 시간만 보면 되기 때문에 end_time만 확인해줘도 됐었다. 

다만 당연히 스택으로 풀려 하다가 append 하는 부분에서 막혀서 검색해보니 heap으로 푼 사람들이 많아서 heap 에 대해 따로 알아 보게 된 시간이였다. (stack으로도 풀어 볼 수 있을 지 좀 더 고민해봐야겠다.) 

2. 에러 

실패 에러

에러 이유 : string_to_number 함수에서 end_time 에 + 10을 해준 상태였는데 이렇게 하니 book_time에 종료 시간이 다른 시작 시간과 겹치는 것 같았다. 
string_to_number("18:00") 이면 18:10 을 변환하게 되는데 이 부분이 다른 배열에서 시작시간과 겹치는 것 같았다. 그래서 일부는 맞고 일부는 틀린 것 같았다. 아예 end_time을 계산하고 + 10을 해주는 방식으로 수정하니 동작이 되었다. 

 

3. 정답 코드

성공 코드

4. 시간복잡도 & 공간복잡도
sort를 통해서 정렬을 사용했기 때문에  O(NlogN) , 그리고 반복문을 돌렸기 때문에 O(N) 그래서 더하면 결국 O(NlogN)이 될 것이고 공간복잡도는 book_time과 rooms의 길이에 영향을 받으므로 O(N)이 될 것이다. 

 

5. 피드백
1) heap : 여기서는 최소 힙(min-heap)을 사용했는데 파이썬에 있는 heapq 을 사용했다. 

heap은 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한다.

• 최소 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙
• 최대 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙

2) 파이썬 heapq 문법 :

• heapq.heappush(heap, item) : item을 heap에 추가
• heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨.