2018 카카오 코딩테스트 - 추석 트래픽, 파이썬

문제

1. 로그 문자열이 들어있는 lines 배열이 주어질 때 초당 최대 처리량을 리턴하라

풀이과정

1. 시간복잡도 고려 : 크게 고려할 필요 없음

   lines 배열은 N(1 ≦ N ≦ 2,000)

2. 문제 조건 확인

   2016-09-15 hh:mm:ss.sss 형식, 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초" 동안 처리된 요청을 의미

기준 시간, 시작 시간, 끝 시간 지정이 애매한데 예제 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. 각 로그마다 [시작시간, 끝시간] 을 구한 후 각각을 기준 시간(1초 시작시간)으로 고려한다. 각 기준시간마다 반복문을 돌려 각 로그가 포함되는지(처리되는지) 확인한다. 처리 되는 기준은 기준시간 시작시간, 기준시간 종료시간(시작시간 + 999) 바깥에 로그가 있지 않으면 된다. 기준 시간 마다 처리 로그 수를 cnt_lst 배열에 저장한 후 최대값을 리턴해준다.

코드

def log_to_time(log) :
  S, T = log.split(" ")[1], log.split(" ")[2]
  h_s = int(S.split(":")[0]) * 3600
  m_s = int(S.split(":")[1]) * 60
  s = S.split(":")[2]
  s = int(s.split(".")[0]) + int(s.split(".")[1])/1000

  end = (h_s + m_s + s) * 1000
  if "." not in T :
      start = end - int(T[:-1])*1000 + 1
  else :
      T = int(T.split(".")[0]) + int(T.split(".")[1][:-1])/1000
      start = end - T*1000 + 1
  return [start, end]

def return_cnt(time, time_lst) :
    cnt = 0
    left = time
    right = time + 999
    for t in time_lst:
        start, end = t[0], t[1]
        if not (left > end or right < start) :
            cnt += 1
    return cnt

def solution(lines):
    time_lst = []
    for log in lines :
        time_lst += [log_to_time(log)]

    cnt_lst = []
    for time in time_lst :
        cnt_lst += [return_cnt(time[0], time_lst)]
        cnt_lst += [return_cnt(time[1], time_lst)]

    return max(cnt_lst)

개선점

다른 사람 풀이 보니 시간처리 코드가 더 깔끔했다.
깔끔은 차치하고 기준시간, 끝시간, 시작시간 등을 선정하고 포함여부를 빨리 캐치하는게 중요한 것 같다.