[프로그래머스 level 3] 추석 트래픽 (Python)

문제에서 주어진 그림 덕분에 해결방법을 바로 떠올릴 수 있었다.

 

1. 우선 문자열로 주어진 시간을 파싱해서 초단위로 모두 바꾼다.  -> 문자열 파싱 때문에 Python 을 사용했다
   그리고 위 그림처럼 시작 시간과 종료 시간을 튜플로 묶어서 리스트에 넣는다. (시간 구간을 원소로 하는 리스트 생성)
   
   
2. 구간의 시작시간에 대해 오름차순 정렬한다.
   
   
3. 구간 리스트를 순회하면서 구간을 우선순위 큐에 삽입한다.
   우선순위 큐는 구간의 종료 시점에 대해 오름차순 정렬되어 있다.
   {구간의 시작 시간 - 1초} 값이 우선순위 큐의 top 원소의 종료 시간보다 같거나 크다면 1초 구간 내에 없다는 뜻이므로 우선순위 큐의 top 원소를 pop 한다.
   
   따라서 우선순위 큐에 원소가 있다면 다들 1초 간격 내에 존재하는 구간인 것이다.
   매 순회마다 우선순위 큐의 개수의 최댓값으로 답을 갱신해준다.

 

 

최종 코드

import heapq

def solution(lines):
    answer = 0
    
    period = []
    
    for line in lines:
        dtime = line[11:]
        ed_last = dtime.split(' ')
        ed = ed_last[0]
        last = float(ed_last[1][0:-1])
        sec = float(ed[0:2]) * 3600.0 + float(ed[3:5]) * 60.0 + float(ed[6:])
        
        period.append((sec-last+0.001, sec))
    
    period.sort(key=lambda t:t[0])
    
    pq = []
    
    for time in period:
        st = time[0]
        while(pq):
            if st - 1 >= pq[0][1][1]:
                heapq.heappop(pq)
            else:
                break
                
        heapq.heappush(pq, (time[1], time))
        answer = max(answer, len(pq))
    
    return answer