반응형
https://programmers.co.kr/learn/courses/30/lessons/17676
import re
import heapq
def solution(lines):
info = []
min_start = 9876543210
max_finish = -1
for line in lines:
date, finish, time = line.split(' ')
hh, mm, ss, sss = map(int, re.split('[:.]', finish))
mm += hh*60
ss += mm*60
sss += ss*1000
finish = sss
time = int(float(time.split('s')[0])*1000)
start = finish - time + 1
if start <0:
start = 0
min_start = min(min_start, start)
max_finish = max(max_finish, finish)
heapq.heappush(info, [start, finish])
answer = 0
t = min_start
box = []
box_count = 0
while t < max_finish+1:
while info and info[0][0] <= t+999:
log_start, log_finish = heapq.heappop(info)
heapq.heappush(box, log_finish)
box_count += 1
answer = max(answer, box_count)
while box and box[0] == t:
heapq.heappop(box)
box_count -= 1
if info and box:
t = min(info[0][0], box[0])
elif info:
t = info[0][0]
elif box:
t = box[0]
else:
break
return answer
일단 모든 로그를 훑으며 시작시간(start)와 종료시간(finish)를 구해준다.
이때 min_start, max_finish를 추가로 찾아주어 이후 탐색의 범위를 줄인다.
이 문제에서는 힙 자료구조가 결정적인 역할을 한다.
info에는 [시작시간, 종료시간] 형태로 데이터가 들어가 있다.
시간을 의미하는 t는 min_start에서부터 시작하도록 해주면 된다.(t는 밀리세컨드 단위!)
반복문 속에서 우선 info를 살펴보며 필요한 데이터를 box 안으로 넣어주는 작업을 한다.(힙으로 빼서)
여기서 필요한 데이터란 현시각 t로부터 1초 안의 범위인 t+999까지 안에 시작시간이 포함되는,
즉 쉽게 말해 1초 구간 속에서 시작하는 로그다.
이들은 전부 카운트가 되어야 하므로 box_count 값을 1올려준다.
그렇게 구해진 box_count를 answer와 비교하며 답을 구해주면 된다.
근데 이 중 종료시간이 다 된 로그들은 box에서 빼주어야 한다. 이때도 힙 팝으로 빼준다.
t는 info, box를 살펴보며 최대한 효율적으로 점프하게 해준다.
댓글