[맛있는물회] <2018 카카오> "추석 트래픽"

문제 조건

---

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

 

Input

---

• 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를 기준으로 오름차순 정렬되어 있다.

 

Output

---

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

 

생각한 아이디어

---

조금 복잡하게 푼 듯 하지만 그래도 로직을 생각해두고 푸니깐 깔끔하게 풀렸따

 

근데 start_list를 정렬안하고 접근해서 맨첨에 2개 틀렸었는데 정렬하니깐 잘 풀림!

 

로직은 이러하다

먼저 시간을 받은다음에 시작시간을 계산하고 start, end 리스트를 만든다

 

만들어진 리스트를 통해 비교한다

 

start ~ start + 1 구간과 

end ~ end +1 구간 이렇게 두개를 잡고 카운팅을 했다

 

먼저 구간안에 값이 들어와야 하기 때문에 구간을 잡고 2중 포문을 돌면서 완전 탐색을 하였다.

구간안에 있는지 비교하는 것은 지금 생각해보니 위에 처럼 기준을 잡고 그냥 단순 비교하면 될듯,,,

나는 start + 1 이라는 구간을 만들기 보다는 if 문으로 비교를 했다.

그래서 코드가 길어진 것 같다

와... 다른 풀이에서 그냥 h,m,s를 싹 초로 변환해서 계산한 사람이 있다. 그렇게 되면 내가 만든 compare 함수가 전혀 필요가 없다!! 

 

소스코드

import copy
 
def cmp_time(start,cmp): #start 가 크거나 같으면 1, 작으면 0
    #단순 시간 비교 h,m,s 각각 비교
    if start[0] > cmp[0]:
        return True
    elif start[0] < cmp[0]:
        return False
    else:
        if start[1] > cmp[1]:
            return True
        elif start[1] < cmp[1]:
            return False
        else:
            if start[2] >= cmp[2]:
                return True
            else:
                return False
 
def cmp_time2(start,cmp): #start 가 크거나 1, 작거나 같으면 0
    #단순 시간 비교 h,m,s 각각 비교
    if start[0] > cmp[0]:
        return True
    elif start[0] < cmp[0]:
        return False
    else:
        if start[1] > cmp[1]:
            return True
        elif start[1] < cmp[1]:
            return False
        else:
            if start[2] > cmp[2]:
                return True
            else:
                return False
 
def solution(lines):
    MAX = -99999999999
    traffics = []
    start_list = []
    for line in lines:
        tmp = list(map(str,line.split()))
        traffics.append(tmp[1:])
    for traffic in traffics:
        time = traffic[0]
        t = float(traffic[1].replace('s',''))
        h,m,s = int(time[:2]),int(time[3:5]),float(time[6:])
 
        if s-t+0.001 >= 0:
            start = [h,m,round(s-t+0.001,3)]
        else:
            if m-1>=0:
                start = [h,m-1,round(s-t+0.001+60.000,3)]
            else:
                start = [h-1,m-1+60,round(s-t+0.001+60.000,3)]
        end = [h,m,s]
        start_list.append([start,end])
    
    start_list = sorted(start_list,key=lambda k: (k[0][0],k[0][1],k[0][2]))
    
    for s in start_list: #모든 스타트 살핌
        cnt = 0
        for c in start_list:
            if cmp_time(s[0],c[0]) and cmp_time(c[1],s[0]):
                cnt +=1
            elif cmp_time(c[0],s[0]):
                tmp = copy.deepcopy(s[0])
                tmp[2] += 1 #1초 증가
                if cmp_time(c[0],tmp):
                    MAX = max(cnt,MAX)
                    break
                else:
                    cnt +=1
        MAX = max(cnt,MAX)
 
    for s in start_list: #모든 엔드 살핌
        cnt = 0
        for c in start_list:
            if cmp_time(s[1],c[0]) and cmp_time(c[1],s[1]):
                cnt +=1
            elif cmp_time(c[0],s[1]):
                tmp = copy.deepcopy(s[1])
                tmp[2] = round(tmp[2] + 1 - 0.001,3) #1초 증가
                if cmp_time2(c[0],tmp):
                    MAX = max(cnt,MAX)
                    break
                else:
                    cnt +=1
        MAX = max(cnt,MAX)
    return MAX
 
if __name__ == "__main__":
    print(solution(    ["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"]))
 
'''
[
'2016-09-15 01:00:04.001 2.0s',
'2016-09-15 01:00:07.000 2s'
]
'''

 

*파이썬 문법 정리