[프로그래머스] 추석 트래픽 / 파이썬

문제 설명

추석 트래픽

이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 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.0011초 동안 최대 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초 구간은 여러 개 존재할 수 있으므로 이 문제에서는 구간이 아닌 개수만 출력한다.

  

풀이

문자열 처리문제이다.
딱히 알고리즘을 보는 문제는 아니고, 구현력을 확인하는 문제이듯하다.
시간을 모두 second 단위로 바꾸어야 계산이 쉬워진다.

second로 바꾸었을 때 소수점이 생기는데, 이는 부동소수점 이슈 때문에 주의해야한다.
따라서 나는 모든값이 1000을 곱해 ms 단위로 바꿨다.

그 후 시작시간, 종료시간을 구한다.
조금 생각해보면, 정답이 되는 최대 개수는
특정한 요청의 시작시간 ~ 시작시간 + 1000ms - 1ms, 종료시간 ~ 종료시간 + 1000ms - 1ms 에 있음을 알 수 있고
따라서 정답이 될 수 있는 모든 시간의 경우를 다 생각해보면 된다.

def isIn(start, times):
    # 특정 시간 start가 주어졌을 때, 몇 개의 시간이 있는가?
    ret = 0
    end = start + 1000 - 1
    for time in times:
        if start <= time[1] and end >= time[0]:
            ret += 1
    return ret

def solution(lines):
    times = []
    for line in lines:
        p = line.split(' ')
        end = p[1].split(':')
        end = int(end[0]) * 3600 * 1000 + int(end[1]) * 60 * 1000 + float(end[2]) * 1000
        start = end - (float(p[2][:-1]) * 1000) + 1
        times.append((start, end))

    ret = 0
    for time in times:
        start, end = time
        ret = max(isIn(start, times), ret)
        ret = max(isIn(end, times), ret)

    return ret