프로그래머스 추석트래픽

https://programmers.co.kr/learn/courses/30/lessons/17676

처음 문자열 파싱하는데 적응이 안되어 있어서 시간이 좀 걸렸다.
문자열을 파싱한 후, 시작시간과 마침시간을 함께 저장하였다.

문제 핵심 로직

ms단위로 시간을 바꾼 뒤, 1초의 크기의 윈도우를 ms단위로 이동시키면 시간*n^2만큼의 시간복잡도가 걸리게 된다.
1ms단위로 시간을 움직인다고 생각하고 윈도우를 움직이면서 처리량의 변화를 그래프로 상상해보자.
그래프로 상상해보면, 어떤 로그의 시작지점, 끝지점에서 변화가 생기는 것을 확인할 수 있다.

def solution(lines):
    timetable = []
    answer = 0
    for line in lines:
        timetable.append(TimeToMs(line))
    print(timetable)
    for time in timetable:
        answer = max(answer,getThrouput(timetable, time[0]))
        answer = max(answer,getThrouput(timetable, time[1]))
    return answer

def TimeToMs(line): // 문자열 처리
    line = line.split(' ')
    h,m,s = line[1].split(':')
    duration = line[2].split('s')
    duration = int(float(duration[0]) * 1000)
    h = int(h) * 60 * 60 * 1000
    m = int(m) * 60 * 1000
    s,ms = s.split('.')
    s = int(s) * 1000
    ms = int(ms)
    end = h+m+s+ms
    start = end - duration + 1
    return [start, end]

def getThrouput(timetable,start): // 특정 윈도우에 걸리는 로그 개수 찾기
    end = start + 1000
    answer = 0
    for time in timetable:
        if not(time[1] < start or time[0] >= end):
            answer += 1
    return answer