[프로그래머스] 추석 트래픽 (Python, 2018 카카오 blind recruitment)

프로그래머스

 

---

문제 설명

• 주어진 로그 데이터 분석 후 초당 최대 처리량을 계산해보자
• 초당 최대 처리량 = 1초에 처리하는 요청의 최대 개수

 

입출력

• 입력
  • `lines`: 로그 문자열 배열로, 각 로그 문자열마다 요청에 대한 응답 완료 시간 S와 처리  시간 T가 공백으로 구분됨
    • 예: 2016-09-15 03:10:33.020 0.011s (응답완료 시간 S: 2016-09-15 hh:mm:ss.sss / 처리 시간 T: 0.24s / 2s (와 같이 s로 끝남))
    • "2016년 9월 15일 오전 3시 10분 33.010초"부터 "2016년 9월 15일 오전 3시 10분 33.020초"까지 "0.011초" 동안 처리된 요청
• 출력
  • `answer`: lines에 대한 초당 최대 처리량

 

주의할 점

• 처리 시간이 0.011초로 주어져도 0.001초를 제외한 0.010초로 계산해야 한다는 것 
• 밀리초라는 것 잊지 않기
  • 시간을 밀리초로 바꿀 때 hh:mm:ss.sss 로 주어지기 때문에 ':' 기준으로 split하고, h와 m은 int, s는 float으로 데이터형 변경해야 함

 

풀이 아이디어

• 2021 카카오 코테에 등장한 광고 삽입 문제와 비슷
• 구간합을 이용하자
• 하지만 다른 점은 추석 트래픽 문제는 millisecond 단위까지 계산할 수 있어야 하기에 t초를 배열의 인덱스로 두면 인덱스는 `24 8 3600 * 1000 * 1000`만큼의 길이가 되어 범위가 너무 커지기 때문에 이렇게 풀기는 어려움이 있음
• start_time을 저장한 1차원 배열인 `start_times`와 end_time을 저장한 1차원 배열인 `end_times`를 만들고, 반복문을 돌면서 t초에 오는 요청들을 `cnt`에 추가하고 `answer`에 갱신 (슬라이딩 윈도우 사용)

 

코드

def to_sec(hms):
    h, m, s = hms.split(':')
    h = int(h)
    m = int(m)
    s = float(s)
    return (h*3600 + m*60 + s)*1000

def solution(lines):
    answer = 0
    start_times = []
    end_times = []
    
    for line in lines:
        _, S, T = line.split(' ')
        end_time = to_sec(S)
        period = float(T[:-1]) * 1000
        
        start_time = end_time - period + 1
        start_times.append(start_time)
        end_times.append(end_time)
    
    for i in range(len(lines)):
        cnt = 0
        cur_end = end_times[i]
        window_start = cur_end
        window_end = cur_end + 999
        
        for j in range(i, len(lines)):
            if start_times[j] <= window_end and end_times[j] >= window_start:
                cnt += 1
        
        answer = max(answer, cnt)
    
    return answer