[프로그래머스/카카오 17676] 추석 트래픽 (Python)

2022. 5. 6. 17:26

문제 링크 #

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

개요 #

datetime 라이브러리를 사용해 해결할 수 있는 문제다.

문제 조건 #

트래픽 처리 종료 시간 및 처리 시간이 짝지어진 로그 문자열을 해석하여 초당 최대 처리량을 반환하는 문제다.

문제 해설 #

datetime과 timedelta 모듈을 활용하여 각각의 트래픽 로그에 대한 시작과 끝 시간을 계산한다.
트래픽의 시작 또는 끝을 1초 구간의 시작으로 정의하고 해당 구간에서 시작됐거나 진행 중인 트래픽 수를 합산한다.
합산된 트래픽 수 중에서 최댓값을 초당 최대 처리량으로 판단하여 반환한다.

한계 #

트래픽 로그를 시작 시간과 끝 시간으로 분리하지 않고 시간 범위로 변환할 수 있다면,
굳이 2N 길이의 반복문을 사용하지 않고 교집합 연산을 사용해서 시간 복잡도를 개선할 수 있었을 것이다.

해설 코드 #

python

from datetime import datetime, timedelta

def solution(lines):
    answer = 0
    lines = sorted(map(interpret_log, lines))

    delta = timedelta(seconds=1)
    for start in sum(lines, []):
        t = sum([check_time_range(time_range, start, start+delta) for time_range in lines])
        answer = max(t, answer)
        start += delta

    return answer

def interpret_log(line):
    line = line.split()
    line = [word.split(s) for word, s in zip(line, ['-',':','s'])]
    Y,m,d,H,M,S,ms = list(map(int,line[0]+line[1][:-1]+line[1][-1].split('.')))
    end_date = datetime(Y,m,d,H,M,S,ms*1000)
    duration = line[2][0] if '.' in line[2][0] else line[2][0]+'.0'
    S,ms = list(map(int,duration.split('.')))
    start_date = end_date - timedelta(seconds=S,milliseconds=ms-1)

    return [start_date, end_date]

def check_time_range(time_range, start, end):
    con1 = start <= time_range[0] < end
    con2 = time_range[0] <= start <= time_range[1]
    return con1 or con2