[1차] 추석 트래픽 (lv3)

이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 9월 15일 로그 데이터를 분석한 후 초당 최대 처리량을 계산해보기로 했다. 초당 최대 처리량은 요청의 응답 완료 여부에 관계없이 임의 시간부터 1초(=1,000밀리초)간 처리하는 요청의 최대 개수를 의미한다.

입력 형식

• solution 함수에 전달되는 lines 배열은 N(1 ≦ N ≦ 2,000)개의 로그 문자열로 되어 있으며, 각 로그 문자열마다 요청에 대한 응답완료시간 S와 처리시간 T가 공백으로 구분되어 있다.
• 응답완료시간 S는 작년 추석인 2016년 9월 15일만 포함하여 고정 길이 2016-09-15 hh:mm:ss.sss 형식으로 되어 있다.
• 처리시간 T는 0.1s, 0.312s, 2s 와 같이 최대 소수점 셋째 자리까지 기록하며 뒤에는 초 단위를 의미하는 s로 끝난다.
• 예를 들어, 로그 문자열 2016-09-15 03:10:33.020 0.011s은 "2016년 9월 15일 오전 3시 10분 33.010초"부터 "2016년 9월 15일 오전 3시 10분 33.020초"까지 "0.011초" 동안 처리된 요청을 의미한다. (처리시간은 시작시간과 끝시간을 포함)
• 서버에는 타임아웃이 3초로 적용되어 있기 때문에 처리시간은 0.001 ≦ T ≦ 3.000이다.
• lines 배열은 응답완료시간 S를 기준으로 오름차순 정렬되어 있다.

출력 형식

• solution 함수에서는 로그 데이터 lines 배열에 대해 초당 최대 처리량을 리턴한다.

---

0.001초 간격으로 1초씩 윈도우를 해보는건, 하루의 시간을 0.001초 단위로 잘라 완전탐색해보겠다는 의미와 같다. 대신, 각 로그의 시작시간과 종료시간을 기준으로 1초동안 처리하는 작업의 개수가 달라진다는 점을 이용하면 O(N^2)의 시간복잡도로 문제를 해결 가능하다. 이후에는 구현하는데 어려운점이 없지만, 발상을 떠올리는게 무엇보다 어렵고 핵심이되는 문제이다.

 

from datetime import datetime,timedelta

def solution(lines):
    answer = -int(1e9)
    log = []
    for line in lines:
        line = line.split()
        line[2] = line[2][:-1]
        d = timedelta(microseconds=(10**6)*(float(line[2])-0.001))
        end = datetime.strptime(line[1], '%X.%f')
        start = (end-d)
        log.append((start,end))
        
    for p1,p2 in log:
        result1,result2 = 0,0
        d = timedelta(seconds=1)
        for _start_,_end_ in log:
            if p1-d < _end_ <= p1 or p1-d < _start_ <= p1 or (p1-d >= _start_ and p1 < _end_):
                result1 += 1
            if p2-d < _end_ <= p2 or p2-d < _start_ <= p2 or (p2-d >= _start_ and p2 < _end_):
                result2 += 1
        answer = max(answer,result1,result2)
    
    return answer