2018 KAKAO BLIND RECRUITMENT[1차] 추석 트래픽 (python, 파이썬)

• 문제

추석 트래픽

이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 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 배열에 대해 초당 최대 처리량을 리턴한다.

---

• 입/출력

time	results
["2016-09-15 00:00:00.000 3s"]	1
["2016-09-15 23:59:59.999 0.001s"]	1
["2016-09-15 01:00:04.001 2.0s", "2016-09-15 01:00:07.000 2s"]	1
["2016-09-15 01:00:04.002 2.0s", "2016-09-15 01:00:07.000 2s"]	2
["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"]	7
["2016-09-15 00:00:00.000 2.3s", "2016-09-15 23:59:59.999 0.1s"]	1

---

• 코드

from datetime import datetime

def str2int(time):
    temp = time.split(':')
    temp2 = temp[2].split('.')
    hour = int(temp[0]) * 3600 * 1000
    minute = int(temp[1]) * 60 * 1000
    second = int(temp2[0]) * 1000
    mili = int(temp2[1]) + 1
    
    return hour+minute+second+mili
    
def solution(lines):
    answer = 0
    dic = {}
    
    min_value = 99999999
    max_value = -1
    # 전처리
    for i, v in enumerate(lines):
        temp = v.split(' ')
        end = temp[1]
        time = temp[2][:-1]
        start = str2int(end)-int(float(time)*1000)+1
        end = str2int(end)
        
        if start < min_value:
            min_value = start
        
        if end > max_value:
            max_value = end
        
        dic[i] = (start, end)
        
    go = [(v[0]-min_value+1, v[1]-min_value+1) for k,v in dic.items()]
    dp = [0] * (max_value-min_value+3)
    
    # 처음과 끝을 모두 포함
    for i, j in go:
        start = 1 if i-999 <= 1 else i-999
        dp[start] += 1
        dp[j+1] -= 1
    
    for i in range(1, len(dp)):
        dp[i] = dp[i] + dp[i-1]
    
    return max(dp)

1. time log를 모두 밀리초 단위로 전처리를 진행했다. (str2int)

현재 log에는 end시간과 소요시간만 나와있기 때문에 end-소요시간을 통해 start시간을 구해주었다. 단 여기서 처음과 끝을 모두 포함하기 떄문에 end-소요시간에다가 1을 더해주어야한다.

 

밀리초 단위로 계산을 하면 값이 커지기 때문에 이후 dp배열을 만들어서 계산하게 될 경우 memory낭비가 심하기 때문에 최소값과 최대값을 동시에 찾아준다.

 

2. 이후 밀리초로 바뀐 start, end시간에서 최소값을 빼고 1을 더해줌으로써 1부터 표시하게 만들어주었다.

 

3. 여기서부터 저의 핵심 아이디어입니다!! 저는 dp를 통해 답을 해결하려고 했습니다.

• 문제를 보면 1000밀리초 1초 동안의 많은 처리량을 구하는것이다. 이는 1~1000 / 2~1001 / ... 이렇게 for문을 늘려가면서 모든 트래픽을 하나하나 접근하다보면 100% 시간초과가 나기 때문에 dp배열로 한번에 정보를 담고자 했습니다.
• 예시
  • 561~1200의 처리를 한 트래픽이 있는 경우
    • 1~1000 / 2~1001 ... 다 1초안에 들어온다. 여기서 포인트다 그럼 어디까지가 1초 범위안의 들어오는지를 계산했다. 결국 1~1200의 시작포인트는 561~1200의 트래픽을 처리한것으로 나오는것이다.
  • 1005~1692의 처리를한 트래픽이 있는 경우
    • 999가 넘기때문에 6~1692의 시작포인트가 1005~1692의 트래픽을 처리한것으로 나오는 것이다.
• 결국 start값이 999보다 작으면 1부터 무조건 포함이고 아닐 경우는 999를 빼주면된다. (1000이 아닌것은 처음과 끝을 포함하기 때문이다 사실 이 999, 1000떄문에 은근히 헷갈렸다.)

4. 최종 dp에는 해당 밀리초마다의 처리한 트래픽 개수가 나오게 되기 때문에 list의 최대값을 뽑아내주면 된다.

---

• 출처

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