프로그래머스 48일차 - 호텔 대실

문제 설명
호텔을 운영 중인 코니는 최소한의 객실만을 사용하여 예약 손님들을 받으려고 합니다. 한 번 사용한 객실은 퇴실 시간을 기준으로 10분간 청소를 하고 다음 손님들이 사용할 수 있습니다.예약 시각이 문자열 형태로 담긴 2차원 배열 book_time이 매개변수로 주어질 때, 코니에게 필요한 최소 객실의 수를 return 하는 solution 함수를 완성해주세요.
제한사항
1 ≤ book_time의 길이 ≤ 1,000
book_time[i]는 ["HH:MM", "HH:MM"]의 형태로 이루어진 배열입니다
[대실 시작 시각, 대실 종료 시각] 형태입니다.
시각은 HH:MM 형태로 24시간 표기법을 따르며, "00:00" 부터 "23:59" 까지로 주어집니다.
예약 시각이 자정을 넘어가는 경우는 없습니다.시작 시각은 항상 종료 시각보다 빠릅니다.

 

해설

deque로 풀려다가 리스트가 스택 큐 문제가 아님을 깨닫고 다른사람 풀이를 봤다.

 

정렬 문제 중에 heap 정렬이라는 문제 유형이라고 한다.

문제 자체는 매우 간단하다.

15:00 처럼 나온걸 분으로 만들어서 분끼리 비교를 하는것이다.

 

리스트에서 0번째 요소만 가지고 오름차순 정렬을 한다.

book time 리스트를 가지고 for문을 돌려 요소를 비교하는데,

처음에 아무것도 없을 때에는 첫요소(제일 작은 분)은 무조건 넣고 시작한다.

 

그리고 1개라도 들어있을 경우에는 그때부터 리스트의 [0]번째 요소와 book_time의 [1]번째 요소의 비교를 시작한다.

만약 start가 room[0]요소보다 크다면 기존의 요소를 뺀다.

그렇지 않을 경우 힙에 집어넣는다.

 

 

[["14:10", "19:20"], ["14:20", "15:20"], ["15:00", "17:00"], ["16:40", "18:20"],["18:20", "21:20"]]

 

이렇게 된 거에서 19:20을 room에 넣는다.

end 의 타임을 우선 나열하면 [920, 980, 1020, 1100, 1280]

1100이 room에 들어가는데, 

900 > 1100 아니니까 room에 넣고

900 > 1100 아니니까 room에 넣고

1120 >1100 이니까 ["14:10", "19:20"]을 뺀다.

 

그렇게 for문을 반복한다.

 

 

힙이 처음이라 좀 이해하기 시간이 걸렸지만 deque랑 별로 차이가 없는것 같다.

 

---

Heap은 최댓값, 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안되었으며 완전 이진 트리 (Complete Binary Tree)를 기본으로 가집니다. 즉, 데이터가 입력이 되면 가장 말단에서 왼쪽부터 차례대로 채워져 나갑니다.

 

Insert

데이터 삽입은 아래와 같은 순서를 지킵니다.

1. 데이터 삽입은 왼쪽에서 오른쪽 순서로 완전 이진 트리를 구성
2. 입력된 데이터와 부모 노드의 값을 비교
3. 부모보다 작다면(최소힙 기준) 서로의 자리를 변경
4. 2~3번을 부모보다 클때까지 반복

delete

힙에서 삭제는 루트 노드를 지우는 것이 일반적입니다.

데이터 삭제는 아래와 같은 순서를 지킵니다.

1. 루트노드 삭제
2. 트리의 말단에서 가장 오른쪽에 있는 노드를 루트로 승격
3. 루트 노드가 된 데이터와 두 자식 노드의 값을 비교하여 가장 작은 값과 위치 변경

 

https://brownbears.tistory.com/550