[알고리즘] [1차] 추석 트래픽 문제 풀이 (Python)

문제보기

풀이

로그들의 리스트가 완료 순서대로 정렬되어 있고 1초간 처리량의 최대값을 구하는 문제이다.

요청이 완료되는 시점(해당 요청을 포함)부터 1초동안 처리 중인 요청의 수를 계산해서 최대값을 찾아 반환하는 방법으로 풀이를 했다.

요청은 "2016-09-15 01:00:04.001 2.0s"와 같이 날짜, 요청완료시각, 처리소요시간 순으로 공백으로 구분되어 문자열로 주어진다.

요청데이터를 가공해서 시간을 비교해야하기 때문에 각 요청의 완료 후 1초, 요청완료시간에서 처리소요시간을 뺀 요청시작시간을 구하는 함수가 필요하다.

요청완료순으로 정렬된 리스트를 순회하면서 기준이되는 요청완료시점부터 1초 후 시각보다 이 후 요소들의 요청시작시각이 작은(빠른) 요청의 경우 1초동안 요청처리가 포함된다고 간주되고 카운트를 하고 최종적으로 1초동안 가장 많은 요청이 처리되는 수를 계산하고 반환한다.

코드

def start_time(log, t):
    hh, mm , ss = log
    ss = round(float(ss) - float(t) + 0.001, 3)
    if ss < 0:
        mm = int(mm)-1
        ss += 60
        if mm < 0:
            hh = int(hh)-1
            mm = mm + 60
            if hh < 0:
                return [0, 0, 0]
    return [int(hh),int(mm),ss]


def after_1sec(log):
    hh, mm , ss = log
    ss = round(float(ss) + 0.999, 3)
    if ss >= 60:
        ss = round(ss - 60, 3)
        mm = int(mm) + 1
        if mm >= 60:
            mm -= 60
            hh = int(hh) + 1
            if hh >= 60:
                return [23, 59, 59.999]
    return [int(hh),int(mm),ss]

def is_contain(end, start):
    if end[0] < start[0]: return False
    if end[1] < start[1]: return False
    if end[2] < start[2]: return False
    return True
    
def solution(lines):
    answer = 1
    lines = list(map(lambda x: [x.split()[1].split(':'), x.split()[2][:-1]], lines))
    for i in range(len(lines)-1):
        cnt = 1
        for j in range(i+1, len(lines)):
            if is_contain(after_1min(lines[i][0]), start_time(lines[j][0], lines[j][1])):
                cnt += 1
        answer = max(answer, cnt)
    return answer