문제
이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 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 배열에 대해 초당 최대 처리량을 리턴한다.풀이과정
나보다 더 멋진 풀이들이 많겠지만.. 진짜 거의 3시간 가까이 걸렸다.
Lv3으로 넘어가고 나서 이렇게 시간이 오래걸리다니 😥😥
내 풀이의 핵심만을 설명하자면,
1.주어진 입력을 언제부터 언제까지 처리된 요청인지로 변환한다.
ex.
Input: "2016-09-15 03:10:33.020 0.011s"
변환 (Traffic): [03:10:33.010, 03:10:33.020]2.1에서 구한 언제부터 언제까지, 즉, 요청이 처리된 기간의 처음과 끝 부분에서부터 1000ms간격을 모두 구해서, timestamp배열에 저장한다.
ex.
[03:10:33.010, 03:10:33.020] 의 경우,
timestamp에 추가될 값:
[03:10:32.011, 03:10:33.010]
[03:10:33.010, 03:10:34.009]
[03:10:32.021, 03:10:33.020]
[03:10:33.020, 03:10:34.019]3.각 timestamp에 대해서 timestamp에 조금이라도 걸치면 cnt를 증가시킨다. 즉, timestamp의 시작점과 끝점을 s,e라 하고 1에서 변환한 traffic 구간의 시작과 끝을 []로 표시한다면,] < s와 e < [ 경우를 제외한 모든 경우에 cnt를 증가시킨다.
4.가장 큰 cnt값을 answer에 저장하여 리턴한다.
소스코드
소요 시간 02:50:40 이상...
def calcTime(h,m,s, T):
h, m, s, T = int(h), int(m), float(s), float(T) #형변환
if s < T: #s=00.464 T=1.466과 같은 경우
m -= 1
if m < 0:
m = 59
h -= 1
s += 60.0
return [h, m, round(s-T+0.001,3)]
# 1초 뒤 시간을 구함
def getAfter(time):
h,m,s = time
r_h, r_m, r_s = h, m, round(s + 1.000 - 0.001,3) # before_hour, before_min, before_sec
if r_s >= 60.0:
r_m += 1
r_s -= 60.0
if r_m >= 60:
r_h += 1
r_m -= 60
return [r_h, r_m, r_s]
# 1초 전 시간을 구함
def getBefore(time):
h, m, s = time
r_h, r_m, r_s = -1, -1, -1.00
r_h, r_m = h, m
if s < 1.00:
r_s = round(s + 60 - 1.000 + 0.001,3)
r_m -= 1
if r_m < 0:
r_h -= 1
r_m += 60
else:
r_s = round(s - 1.000 + 0.001, 3)
return [r_h, r_m, r_s]
def compare(t1, t2):
#t1 = [h, m, s], t2 = [h,m,s] 리스트로 들어온 시간의 대소를 비교
# t1이 더 작으면 True를 리턴
h1, m1, s1 = t1 #21 0 0.464
h2, m2, s2 = t2 #20 59 58.233
if h1 < h2:
return True
if h1 == h2 and m1 < m2:
return True
if h1 == h2 and m1 == m2 and s1 < s2:
return True
return False
def solution(lines):
answer = 0
traffic = list()
for i in range(len(lines)):
date, time, T = lines[i].split(' ')
T = T[:-1] #뒤의 s 제거
h, m, s = time.split(':')
traffic.append([calcTime(h,m,s,T),[int(h),int(m),round(float(s),3)]])
timestamp = list() #기준 시간대별로 앞 뒤로 1000ms 간격을 모두 timestamp에 저장함
for i in range(len(traffic)):
timestamp.append([getBefore(traffic[i][0]), traffic[i][0]])
timestamp.append([traffic[i][0], getAfter(traffic[i][0])])
timestamp.append([getBefore(traffic[i][1]), traffic[i][1]])
timestamp.append([traffic[i][1],getAfter(traffic[i][1])])
while timestamp:
s, e = timestamp.pop(0) #start, end
cnt = 0
for i in range(len(traffic)):
if compare(traffic[i][1],s) or compare(e, traffic[i][0]):
continue
cnt += 1
if answer < cnt:
answer = cnt
return answer