[백준-파이썬] 22867: 종점

문제 보러 가기!

문제 🤔

버스가 종점에 들어온다. 종점에 와서는 정비를 해야 하기 때문에, 버스 정비 공간에 가야 한다. 버스가 종점에 들어오는 시각, 종점에서 나가는 시각이 주어진다. 버스 정비 공간이 최소로 몇 개 필요한지 계산하는 문제 즉, 한번에 종점에 버스가 최대 몇 개까지 있는지를 계산하는 문제이다!
(단, 같은 시각에 종점에 들어오는 버스- 나가는 버스가 있으면 먼저 나간 후에 출발한다)

아이디어 😍

일단은 버스가 들어오고 나가는 시각이 복잡하게 들어오기 때문에(HH:MM:SS.sss) 편하게 바꿔줬다. 다행히도 들어오는 숫자의 자릿수는 늘 같으니까, 시각에 곱하기 천만 + 분에 곱하기 십만 + 초에 곱하기 천+ 밀리초는 그대로 받아왔다. 그러면 하나의 숫자가 되어서 다루기 편하다.

그리고는 뭔가.. 그림으로는 어떻게 할지 파악이 되는데 어떻게 풀어야 할지 막막했다 ㅠㅠ

그러다가 이 문제가 강의실 배정 문제와 비슷하다는 포스팅 을 보았다.
그래서 [강의실 배정] (https://www.acmicpc.net/problem/11000)문제를 찾아보았고, 그 문제를 우선순위 큐를 활용해서 풀 수 있다는 아이디어를 알게 되었다. 그래서 먼저 강의실 배정 문제를 풀었고, 종점 문제를 풀었다. 풀어보니 진짜 비슷한 것 같다!

출발시각, 도착시각을 튜플로 받아서 리스트에 넣는다.
-> 출발 시각이 이른 것부터 쭉 정렬을 한다.
-> 우선 순위 큐에다가 출발 시각이 가장 이른 버스의 (나가는 시각, 들어오는 시각)을 넣는다.
-> 쭉~~ 본다. (출발 시각 기준으로 시간이 간다고 생각해도 될 것 같다.)
일단 가장 빨리 나가는 버스를 매번 heappop으로 본다.

1) 그 버스가 나가는 시각보다, 이번에 들어오는 버스가 더 빨리 오면 종점에 같이 있어야 하는 것이니까 bus_one_time을 하나 더한다. 그리고 가장 빨리 나갈 예정인 버스도, 이번에 들어오는 버스 출발 시각을 기준으로는 나가지 않은 거니까 다시 큐 안에 넣는다. 또 이번 버스도 (나가는 시각, 들어오는 시각)으로 큐 안에 넣는다.
2) 가장 빨리 나갈 예정인 버스가, 이번에 오는 버스보다 빨리 나가면
같이 종점에 있지 않아도 되니까 bus_one_time을 가만히 둔다. (하나는 빠져 나가고, 하나는 더 들어온 거니까 그냥 가만히 두면 됨) 이번에 오는 버스가 들어오는 시각 기준으로, 가장 빨리 나갈 예정인 버스는 나간 거니까 그냥 둔다. (팝했으니까) 이번에 들어온 버스는 큐 안에 넣어준다.

코드 👩‍💻

import heapq
import sys

input = sys.stdin.readline

N = int(input())
buses = []
for _ in range(N):
    in_time, out_time = input().split()
    # 시각, 분, 초, 밀리초를 계산해서 하나의 숫자로 해준다.
    in_time_final = int(in_time[9:]) + int(in_time[6:8]) * 1000 + int(in_time[3:5]) * 100000 + int(
        in_time[:2]) * 10000000
    out_time_final = int(out_time[9:]) + int(out_time[6:8]) * 1000 + int(out_time[3:5]) * 100000 + int(
        out_time[:2]) * 10000000
    buses.append((in_time_final, out_time_final))

# 출발 시각 이른 것부터 정렬
buses.sort()

Q = []
heapq.heappush(Q, (buses[0][1], buses[0][0]))  # 나가는 시각, 들어오는 시각
bus_one_time = 1

for i in range(1, N):  # 하나씩 쭉 보기
    fast_out = heapq.heappop(Q)  # 가장 빨리 나가는 버스
    if buses[i][0] < fast_out[0]:  # 가장 빨리 나가는 버스가 나가는 시각보다, 이번에 들어오는 버스가 더 빨리 들어오면
        bus_one_time += 1  # 종점에 같이 있어야 하니까 하나 더함
        heapq.heappush(Q, fast_out)  # 가장 빨리 나가는 버스가.. 안 나갔으니까 더해줌
        heapq.heappush(Q, (buses[i][1], buses[i][0]))  # 이번 버스도 들어옴
    else:  # 가장 빨리 나가는 버스가, 이번에 들어오는 버스보다 빨리 나가면
        heapq.heappush(Q, (buses[i][1], buses[i][0]))  # 이번 버스 들어옴
print(bus_one_time)