글 작성자: 택시 운전사
반응형

[프로그래머스] 📊 추석 트래픽 - [1차] 2018 카카오 블라인드 채용 / 파이썬 / python / KAKAO BLIND RECRUITMENT

📊 추석 트래픽

문제설명

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

😃 나의 풀이

def time2durationSec (time):
    lst = time.split(' ')
    end = lst[1]
    duration = lst[2]
    # print(end, duration)
    lst2= end.split(':')
    hour = int(lst2[0])*1000
    minu = int(lst2[1])*1000
    sec = int(lst2[2][0:2] + lst2[2][3:])
    micsec = hour*3600 + minu*60 + sec
    lst3 = duration[:-1].split('.')
    if len(lst3)>1:
        duration2 = int(lst3[0])*1000 + int(lst3[1]+('0'*(3-len(lst3[1]))))
    else: duration2 = int(lst3[0])*1000

    # print([micsec-duration2, micsec])
    return [micsec-duration2 + 1, micsec]

def checkProcessNum (time, lst):
    num = 0
    start = time
    end = time + 1000
    for duration in lst:
        if not (duration[1] < start or duration[0] >= end):
            num += 1
    return num

def solution(lines):
    answer = 0
    lst = []
    count = []
    for string in lines:
        lst.append(time2durationSec(string))
    print(lst)
    for i in lst:
        print(i)
        count.append(checkProcessNum(i[0], lst))
        count.append(checkProcessNum(i[1], lst))

    return max(count)

우선적으로 했던 것은 시간 형식을 밀리세컨드 수준까지 낮추는 함수를 만드는 것이었다. 저번의 셔틀버스문제에서와 마찬가지로 가장 최소 단위로 맞춰서 계산을 진행하는 게 여러모로 편하다. 시간을 나는 걸린 시간까지 밀리세컨드로 변환하여 로그의 [시작 시간, 끝나는 시간]에 해당하는 배열을 반환하도록 time2durationSec를 짰다.

다음은 이전 셔틀버스문제에서의 접근법과 비슷하게 백트랙킹 알고리즘을 썼다. 시작 시간과 끝나는 시간이 있는 로그들의 배열에서 초당 최대 처리량이 최고가 되는 시작 시간은 로그들의 시작 혹은 끝 중에 있는 것이 확실하다. 만약 이 접근법을 사용하지 않고 로그의 시작부터 끝까지 1밀리세컨트마다 움직이게 되면 time(ms) * n^2가 걸리게 되고 시작점과 끝점만 사용하면 2 * n^2만 걸리기 때문에 시간이 확연히 줄어들게 된다.

다음으로 특정 초 안에 최대 처리량이 있는 지 확인하는 것보다 확실하게 존재하지 않는 경우의 역을 취하는 방법이 경우의 수가 더 적기 때문에 not (duration[1] < start or duration[0] >= end) 이런 식으로 짜보았다.

결과적으로 count라는 배열에 후보군에 초에 맞는 최대 처리량이 저장되고, 그 중 가장 큰 값을 return하고 마무리한다.

사용했으면 좋았을 것들

  • split으로 나눌 때, h, m, s = time.split(':') 이런 식으로 짜는 것
  • datetime 파이썬 내장 라이브러리 사용
반응형