[프로그래머스 1차 추석트래픽] 파이썬 풀이

• [프로그래머스 1차 추석트래픽] 파이썬 풀이
  • 문제
  • Keypoints
  • Solution
  • References

[프로그래머스 1차 추석트래픽] 파이썬 풀이

문제

Traffic에 대한 정보가 주어질 때, 임의의 1초 구간에서 가장 많은 트래픽을 세는 문제.

Keypoints

• 하나의 트래픽의 처리가 끝나고 다음 트래픽이 1초 안에 시작한다면, 두 개는 1초의 구간 안에 놓이게 된다.
• 시작 시간으로 정렬하고, 끝나는 시간을 추적한다.
• 시작하는 시간으로부터 끝나는 시간까지 1초 밖으로 멀어진다면 끝나는 시간은 더이상 추적할 필요가 없다.
• Heap을 사용해서 끝나는 시간을 추적한다.

Solution

import re 
from heapq import heapify, heappop, heappush

def solution(lines):
    heap = []
    heapify(heap)
    lines = [i.split() for i in lines]  # [(day, time, duration) tuple]

    for i in range(len(lines)):
        lines[i][2] = float(re.sub("[s]","",lines[i][2]))   # remove s
        temp = list(map(float, lines[i][1].split(":")))     # split hour, minute, sec
        lines[i][1]=temp[0]*60*60 + temp[1]*60 + temp[2]    # convert hour minute -> sec

    times = [(end-duration+0.001, end) for _,end,duration in lines]  # [(start, end) tuples]
    times.sort(key=lambda x:x[0])       # sort by start time

    count = 0 
    for start, end in times:
        while heap: 
            if heap[0]<= start-1:  # remove 'end time' before 1 sec
                heappop(heap)
            else:
                break 
        heappush(heap, end)
        count = max(len(heap), count)

    return count

References

Problem Link