[Python] 추석 트래픽 / 시간 tip

문제

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

 

입출력 예제

예제1

• 입력: [
  "2016-09-15 01:00:04.001 2.0s",
  "2016-09-15 01:00:07.000 2s"
  ]
• 출력: 1

예제2

• 입력: [
  "2016-09-15 01:00:04.002 2.0s",
  "2016-09-15 01:00:07.000 2s"
  ]
• 출력: 2
• 설명: 처리시간은 시작시간과 끝시간을 포함하므로
  첫 번째 로그는 01:00:02.003 ~ 01:00:04.002에서 2초 동안 처리되었으며,
  두 번째 로그는 01:00:05.001 ~ 01:00:07.000에서 2초 동안 처리된다.
  따라서, 첫 번째 로그가 끝나는 시점과 두 번째 로그가 시작하는 시점의 구간인 01:00:04.002 ~ 01:00:05.001 1초 동안 최대 2개가 된다.

예제3

• 입력: [
  "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
• 설명: 아래 타임라인 그림에서 빨간색으로 표시된 1초 각 구간의 처리량을 구해보면 (1)은 4개, (2)는 7개, (3)는 2개임을 알 수 있다. 따라서 초당 최대 처리량은 7이 되며, 동일한 최대 처리량을 갖는 1초 구간은 여러 개 존재할 수 있으므로 이 문제에서는 구간이 아닌 개수만 출력한다.
  

  

---

풀이

아이디어 자체 감이 안 왔다.

'''
lines 배열에 대한 "초당 최대 처리량"을 리턴하라
초당 최대 처리량: 요청의 응답 완료 여부에 관계없이 임의 시간부터 1초(=1,000밀리초)간 처리하는 요청의 최대 개수

lines에는 응답완료 시간 S(2016-09-15, hh:mm:ss.sss)와 처리 시간 T가 공백으로 구분되어 있음
(S를 기준으로 오름차순)

ex. 2016-09-15 03:10:33.020 0.011s   
    2016년 9월 15일 오전 3시 10분 33.020초까지 "0.011초" 동안 처리된 요청
    
<idea>
기간이 겹쳤다는 걸 어떻게 확인할까
'''
# 정수형으로 시간을 변환하는 코드
def get_time(time):
    hour = int(time[:2]) * 3600
    minute = int(time[3:5]) * 60
    second = int(time[6:8])
    millisecond = int(time[9:])
    return (hour + minute + second) * 1000 + millisecond

# 시작 시간을 구하는 코드
def get_start_time(time, duration):
    n_time = duration[:-1]
    int_duration = float(n_time) * 1000
    return get_time(time) - int_duration + 1

def solution(lines):
    answer = 0 # 최대 처리량
    if len(lines) == 1:
        return 1
    
    start = []
    end = [] # 각 로그가 끝나는 시간을 변환한 값을 저장
    
    for task in lines:
        date, time, duration = task.split()
        # print(date, time, duration)
        start.append(get_start_time(time, duration)) # 별도로 시간 변환 안함
        end.append(get_time(time))
    
    for i in range(len(lines)):
        cnt = 0 # 각 시간마다 처리되는 로그 개수
        cur_end_time = end[i] # 뒤의 로그와 비교
        for j in range(i, len(lines)):
            if cur_end_time > start[j]- 1000:
                cnt += 1
        answer = max(answer, cnt)
    return answer

1. string의 시간 형태로 주어질 때(hh:mm:ss) 대소 비교를 위해 밀리초(millisecond)를 기준으로 정수형으로 바꿔준다.
1 minute = 60 second / 1 hour = 60 minute = 60 * 60 second = 3600 second (hour, minute는 second 기준으로 바꾼 다음에 더 한 후)
1 second = 1000 millisecond (1000을 한 번에 곱해줌)

 

2. 언제 겹치는 지를 확인하기 위해 시작 시간을 구한다.
끝나는 시간과 시작 시간을 모두 포함하기 때문에, 문제에서 나와있는 형태로 시작 시간과 끝나는 시간을 구하기 위해서는 끝 시간에서 구한(get_time(time)) 시간에 duration_time을 빼준 값에 1을 더해야 한다.
- 2 s, 2.0 s 모두를 입력으로 받기 때문에 float로 변환한 후 millisecond 초를 기준으로 하기 위해 1000을 곱한다.

 

3. 시작 시간과 끝나는 시간을 비교한다. 
이 문제에서는 임의의 시간에서 1000밀리초 구간에서 쿼리가 존재하기만 하더라도 처리된 것으로 처리하기 때문에, 단순히 겹치는 것만 확인하여 겹친다면 카운트를 1 증가시키면 된다. 1000 밀리초 떨어진 것을 어떻게 처리하면 좋을까?
start_time[j]를 1000 밀리초 앞으로 당겼을 때, end_time[i]보다 작다면 1000 밀리초 내에 처리된 것으로 생각할 수 있다.
이 때, 주의해야 할 점은 조건이 end_time[i] <= start_time[j] - 1000이 아닌, end_time[i] < start_time[j] - 1000라는 것이다.
end_time[j]가 start_time[i]-100와 같다면 하나의 작업이 끝남과 동시에 시작되기 때문에 둘은 동시에 처리되지 않았다.

 

참고

---

다른 풀이

datetime 모듈을 사용한다.

# 로그 문자열을 계산하기 쉬운 형태로 변환
# 1초 내에 속하는 개수 count

import datetime

def solution(lines):
    """
    Args:
        lines (List[str]) : 로그 문자열 "일자 hh:mm:ss.sss 걸린시간" 
                          〉["2016-09-15 01:00:04.002 2.0s", "2016-09-15 01:00:07.000 2s"]
        answer
            초당 최대 처리량
    """
    preprocessed_logs = []
    for log in lines:
        logs = log.split(" ")
        timestamp = datetime.datetime.strptime(
            f"{logs[0]} {logs[1]}", "%Y-%m-%d %H:%M:%S.%f"
        ).timestamp()

        preprocessed_logs.append((timestamp, -1)) # 종료시간(-1)
        preprocessed_logs.append((timestamp - float(logs[2][:-1]) + 0.001, 1)) # 시작시간(1)


    count = 0
    max_count = 1
    preprocessed_logs.sort(key=lambda x: x[0])

    for i, log_1 in enumerate(preprocessed_logs):
        curr = count
        for log_2 in preprocessed_logs[i:]:
            if log_2[0] - log_1[0] > 0.999:
                break
            if log_2[1] == 1:
                curr += log_2[1]

        max_count = max(max_count, curr)
        count += log_1[1]