[프로그래머스/카카오 블라인드 테스트 2018/python] 추석트래픽

로직

 

로그들을 endtime이 큰 순서대로 탐색하면서

현재 탐색하고 있는 로그보다 endtime이 큰 로그들을 가지고

[현재 로그의 endtime] ~ [현재 로그보다 endtime이 큰 로그의 starttime] 사이의 거리를 체크해서 1초 구간 안에 있는지 확인해준다.

 

현재 로그보다 endtime이 큰 로그들을 모두 체크해주어도 좋지만,

 

그리고 1초 구간 안에 있는지 확인해주는 작업을 보다 효율적으로 처리하기 위해서 최대힙을 사용하였다.

현재 탐색하고 있는 로그보다 endtime이 큰 로그들의 starttime을 최대힙에 넣어 가장 starttime을 가진 로그부터 확인해준다.

 

글로 설명하는건 항상 어렵다😂

 

예를 들어 아래와 같은 상황이 있다고 가정해보자

 

예시

이렇게 되면 최대 힙에서는 start_timeC, start_timeA, start_timeB 순으로 pop이 될 것이다.

(start_time이 더 늦은 순서대로 pop)

 

1) start_timeC - endtime = 2.5 - 2 = 1.5초

👉 로그들 간의 차이가 1초 이상이므로 pop!

2) start_timeA - endtime = 2.5 - 2 = 0.5 1.5초

👉 로그들 간의 차이가 1초 미만이므로 탐색을 멈춘다.

 

그 이후에 비교를 해주지 않아도 되는 이유는

 

✔ 최대힙에 남아있는 나머지 로그들의 start_time들은 이미 비교해준 로그들의 start_time들에 비해 더 앞에 있다.

✔ 최대힙에 남아있는 나머지 로그들의 end_time들은 현재 로그의 end_time보다 뒤에 있다.

 

✔ 때문에 현재 로그의 endtime과 최초로 pop이 되지 않은 로그 start_timeA 사이에 현재 최대힙에 남아있는 나머지 로그 start_timeB는 반드시 존재한다.

 

 

그리고 한 가지 더 신경써야했던 요소가 1초 구간이었다.

 

우리가 흔히 2부터 5까지 사이의 구간을 구할 때 5 - 2 +1을 하듯이 구간을 계산해주어야 한다.

 

아래 예시로 설명해보면,

 

현재 로그의 start time - 타겟이 되는 다른 로그의 end time  + 0.001 == 구간

 

1) 4.002와 5.001 사이의 구간을 계산할 때는 5.001 - 4.002 + 0.001 을 해주어야 실제 구간이 나온다.

위 계산결과는 1이므로 1초 구간 안에 들어간다.

 

반면, 

2) 4.001과 5.001 사이의 구간을 계산해보면 5.001 - 4.001 + 0.001 이므로 실제 구간은 1.001이 된다.

즉, 1초 구간 밖에 있다.

코드

from datetime import datetime, timedelta
import heapq

def solution(lines):
    answer = 0
    times = []

    for line in reversed(lines):                                        # datetime 형식으로 바꿔주는 작업
        end = datetime.strptime(line[:23], '%Y-%m-%d %H:%M:%S.%f')      # end time
        runtime = float(line[24:].rstrip('s'))                          # run time (duration)
        times.append((end, runtime))                                    # times에 (end time, run time) 형식으로 넣어준다.
    
                                                            
    running_list = []                                       # running_list = 탐색 중인 로그보다 end time이 큰 로그들이 존재하는 max heap
    now = datetime.now()
                                                            
    for end, runtime in times:                              # end time이 큰 순서대로 탐색
        start = end - timedelta(seconds=runtime) + timedelta(milliseconds=1) # 현재 로그의 start time을 구한다.
        
        while running_list:                                 # max heap이 empty가 아닐 때까지 계속 max heap을 확인
            heap_key, start_time = running_list[0]          # max heap에서 가장 start time이 큰 로그를 꺼낸다.
            if start_time - end >= timedelta(seconds=1):   # 현재 로그의 end time heap에서 꺼낸 start time이 1 이상 차이가 나는 경우
                heapq.heappop(running_list)                 # 현재 로그와 1초 구간 안에 있지 않기 때문에 제외시켜준다.
            else: break
        
        heapq.heappush(running_list, (now - start, start))  # max heap을 만들어 주기 위해서 현재시간(now) - start time을 만들어주었다.
        answer = max(answer, len(running_list))             # 최종적으로 현재 로그와 1초 간격으로 차이가 나는 로그들이 heap에 담기게 된다.

    return answer