7. 추석 트래픽(난이도: 상) - Python3.6.1

 

1.풀이방법

초당최대처리량을 계산해야한다. 단위가 최소 0.001초이기 때문에 처음부터 0.001초씩 증가시키면서 스캔하기에는 연산시간이 너무 오래걸리기 때문에 이렇게 풀면 안된다.

모든 로그의 시작과 끝점을 가지고 계산하면 편하다.

모든 로그의 끝부분 부터 이후 1초까지 사이를 계산했다.

*시간복잡도 O(n²)이 나온다. 시간되면 다른 방법을 더 찾아봐야겠다.

2.코드

import datetime

from time import localtime,strftime

def Question7(lines):

    start = []

    end = []

    maxCount = 0

    for i in range(len(lines)): #1

        endTime = datetime.datetime.strptime(lines[i][0:23],'%Y-%m-%d %H:%M:%S.%f')

        processTime = int(float(lines[i][24:30].replace('s',''))*1000000) - 1000

        startTime = endTime + datetime.timedelta(microseconds = -processTime)

        end.append(endTime.strftime('%Y%m%d%H%M%S%f'))

        start.append(startTime.strftime('%Y%m%d%H%M%S%f'))

    for i in range(len(lines)): #2

        startNum = int(end[i])

        endNum = int(end[i])+1000000 - 1000

        count = 0

        for j in range(len(lines)): #3

            if i == j:

                count += 1

            elif startNum <= int(start[j]) <= endNum:

                count += 1

            elif startNum <= int(end[j]) <= endNum:

                count += 1

            elif int(start[j]) <= startNum <= int(end[j]):

                count += 1

            elif int(start[j]) <= endNum <= int(end[j]):

                count += 1

        if maxCount < count: #4

            maxCount = count

    

    return maxCount #5

3.코드설명

#1 각 로그의 시작시간과 끝시간을 계산하고 저장한다.

#2 끝시간 ~ 끝시간+1초 사이에 처리량계산

#3 처리량이 포함되는경우 5가지로 계산한다.

#4 최대처리량 최대값으로 계속 갱신해준다.

#5 처리량을 반환해준다.

*-1000 은 시작시간을 포함하기때문에 0.001초를 보정해준것이다.

4.결과

>>> Question7([ '2016-09-15 01:00:04.001 2.0s', '2016-09-15 01:00:07.000 2s' ])

2

>>> Question7([ '2016-09-15 01:00:04.002 2.0s', '2016-09-15 01:00:07.000 2s' ])

2

>>> Question7([ '2016-09-15 20:59:57.421 0.351s', '2016-09-15 20:59:58.233 1.181s', '2016-09-15 20:59:58.299 0.8s', '2016-09-15 20:59:58.688 1.041s', '2016-09-15 20:59:59.591 1.412s', '2016-09-15 21:00:00.464 1.466s', '2016-09-15 21:00:00.741 1.581s', '2016-09-15 21:00:00.748 2.31s', '2016-09-15 21:00:00.966 0.381s', '2016-09-15 21:00:02.066 2.62s' ])

10