[Python/BOJ] 22867. 종점

https://www.acmicpc.net/problem/22867

22867번: 종점

문제

주행을 마친 버스들이 종점에 들어온다. 종점에 들어온 버스는 버스를 정비하기 위한 자리에 들어간다. 즉, 종점에 버스 4대가 있다면 버스를 정비할 수 있는 공간이 최소 4개 이상 필요하다. 만약 같은 시각에 종점에 들어오는 버스 A와 종점에서 출발하는 버스 B가 있을 경우는 버스 B가 먼저 종점에서 출발하고 그 다음으로 버스 A가 종점으로 들어온다.

버스의 시간표가 매일 동일하며 종점에 들어오는 시각과 나가는 시각이 매일 동일하다.

이번에 버스 시간표가 변경이 되어 버스를 정비하는 공간이 최소 몇 개 이상 필요한지 다시 계산을 해야한다. 이를 도와 계산을 해주자.

입력

첫 번째 줄에는 종점에 들어오는 버스들의 개수 N이 주어진다.

두 번째 줄부터 aN+1번째 줄까지 각 버스가 종점에 들어오는 시각과 종점에서 나가는 시각이 주어진다. 한 버스의 나가는 시각은 들어오는 시각보다 늦다.

주어지는 시각의 형식은 다음과 같다. HH:MM:SS.sss (HH는 시각을, MM은 분, SS은 초, sss 밀리초를 의미한다.)

출력

버스 정비를 위한 공간이 최소 몇 개 이상 필요한지 출력한다.

풀이

Code

import sys
from heapq import heappop, heappush
input = sys.stdin.readline

def solution(n, bus_schedule) :
    # 1. 밀리 초 변환 함수 정의
    def convert(time) :
        # 1-1. 시, 분, 초를 밀리초 값으로 변환
        t = 0
        time = time.replace('.', ':')
        for x, y in zip(map(int, time.split(':')), [3600000, 60000, 1000, 1]) :
            t += x * y
        return t
    # 2. 버스 시간표 정렬
    bus_schedule.sort()
    # 3. 힙 생성
    heap = []
    # 4.
    for IN, OUT in bus_schedule :
        # 4-1. 버스의 진입 시간을 진출 시간을 밀리 초로 변환
        IN, OUT = convert(IN), convert(OUT)
        # 4-2. 버스의 진입 시간이 최소 힙의 진출 시간보다 늦을 경우
        if not heap or IN < heap[0] :
            # 힙에 다음 버스의 진출 시간 삽입
            heappush(heap, OUT)
        # 4-3. 버스의 진입 시간이 최소 힙의 진출 시간보다 같거나 빠를 경우
        else :
            # 힙에서 최솟값 제거
            heappop(heap)
            # 힙에 다음 버스의 진출 시간 삽입
            heappush(heap, OUT)
    # 5. 힙의 길이 출력
    print(len(heap))

if __name__ == "__main__" :
    n = int(input())
    bus_schedule = [list(map(str, input().rstrip().split())) for _ in range(n)]
    solution(n, bus_schedule)