728x90
SMALL
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
def convert_time(time):
h, m = map(int, time.split(':'))
return h * 60 + m
def cal_time(time):
total_m = convert_time(time)
total_m += 10
h, m = divmod(total_m, 60)
return f'{str(h).zfill(2)}:{str(m).zfill(2)}'
def solution(book_time):
answer, rooms = 0, 0
l = len(book_time)
timeline = []
for start, end in book_time:
timeline.append((convert_time(start), 1))
timeline.append((convert_time(cal_time(end)), -1))
timeline.sort()
for _, check in timeline:
rooms += check
answer = max(answer, rooms)
return answer
- 대표적인 그리디 유형의 문제인 장소 배정 문제, 그 중에서도 프로그래머스의 '호텔 배정' 문제입니다.
왜 이렇게 풀었을까?
- 사실 timeline의 문자열들(체크인, 체크아웃 시간)을 바로 정렬하여 문제를 풀 수도 있었지만, 문제에서 '예약 시각이 자정을 넘어가는 경우'가 없었기에 시간을 분 단위로 변환하여 푸는 방법을 택하게 되었습니다.
- 처음 timeline을 정의할 때 체크인을 한 행위는 객실의 수를 1로, 체크아웃을 한 행위는 객실의 수를 -1로 설정하여 추후 누적합으로 전체 객실 수를 계산할 때 사용하였습니다.
- 처음에는 모든 예약들에 대해 for문을 돌리며 객실 수를 파악했었는데, 그러다 보니 시간 복잡도가 증가하는 것을 확인하게 되어 조금 더 효율적인 방법을 고안하다가 생각해낸 것이 누적합이었습니다.
- 조건이 필요없이 그리디와 단순 사칙 연산만 사용하여 O(1)의 시간 복잡도로 객실 수를 파악할 수 있었습니다.
- 나중에 기회가 되면 힙(Heap) 자료구조를 활용하여 조금 더 효율적으로 풀어볼 예정입니다 !!
728x90
LIST
'알고리즘 문제 풀이 > 프로그래머스 (Level 2)' 카테고리의 다른 글
📗 미로 탈출 (0) | 2024.09.20 |
---|---|
📗 무인도 여행 (3) | 2024.09.11 |
📗 두 큐 합 같게 만들기 (4) | 2024.09.06 |
📗 행렬 테두리 회전하기 (2) | 2024.09.05 |
📗 방금그곡 (8) | 2024.08.28 |