[Python] 프로그래머스: 추석 트래픽

추석 트래픽

https://programmers.co.kr/learn/courses/30/lessons/17676

코딩테스트 연습 - [1차] 추석 트래픽

2018 KAKAO BLIND RECRUITMENT

문제 설명

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

핵심 개념

초당 최대 처리량 도출하기

초당 최대 처리량을 알기 위해서는 초당 최대 처리량이 달라지게 만드는 요인인 요청 시작 시점과 완료 시점만 살펴보면 된다.
어떤 요청이 시작되면 초당 최대 처리량은 +1, 요청이 완료되면 -1이 된다.
모든 요청이 시작하고 나면 완료할 일만 남았으므로 9월 15일의 초당 최대 처리량을 알 수 있다.
요청 N개에 대해서 최악의 경우 2N번 요청을 처리하면 되므로 시간복잡도는 O(2N)이 된다.

n초간의 처리량 도출하기

1초간의 처리량을 도출해야 하는데, 이를 시계열과 범위 문제로 생각하면 계산이 복잡해진다.
1초간의 처리량을 도출하기 위해서 모든 요청이 1초 빨리 시작된다고 가정해보자.
이렇게 가정하면 모든 요청 시작 시점과 마지막 요청 시작 시점 이전까지의 요청 완료 시점에서 실행되고 있는 요청의 개수를 확인하면 1초간의 처리량을 도출할 수 있다.
문제를 확장하여 n초간의 처리량을 도출하고 싶으면, 모든 요청이 n초 빨리 시작된다고 가정하면 된다.

 

왜 이것이 가능할까?

 

n초당 최대 처리량을 도출하는 문제는 n초 구간 안에 몇 개의 요청이 있는지 구하는 것과 동일한 문제이다.
전체 시간대 중에서 임의의 n초 구간 안에 k개의 요청이 있다고 가정해보자.
구간 안에 존재하는 k개의 요청이 n초 빨리 시작한다면 구간의 시작 지점에서 k개의 요청은 시작된 상태일 수밖에 없다.

위의 초당 최대 처리량 도출하기와 연결하여 모든 요청의 시작 시점에서 처리중인 요청 개수를 계산하면 전체 구간에서의 초당 최대 처리량을 계산할 수 있다.

풀이

풀이 단계는 다음과 같습니다.

1. lines의 로그 데이터를 분석하여 요청 시작 시점과 완료 시점을 분리한다.
2. 요청 시작 시점과 완료 시점을 정렬하여 queue에 넣는다.
3. 요청 시작 시점이 남아있다면, 시작 시점과 완료 시점을 비교하여 더 작은 쪽을 반영한다.
   • 단, 시작 시점과 완료 시점이 같다면 시작 시점은 -1초가 되어있는 상태이므로 완료 시점을 먼저 반영한다.

from collections import deque

def solution(lines):
    response_start = deque()
    response_end = deque()
    for line in lines:
        line = line.split()
        time_end = line[1]
        time_lapse = line[2]
        
        time_end = 3600 * int(time_end[:2]) + 60 * int(time_end[3:5]) + float(time_end[6:])
        time_lapse = float(time_lapse.replace("s", "")) - 0.001
        
        time_start = round(time_end - time_lapse - 1, 3)
        
        response_start.append(time_start)
        response_end.append(time_end)
    
    response_start = deque(sorted(response_start))
    response_end = deque(sorted(response_end))

    traffic = 0
    max_traffic = 0
    while response_start:
        if response_start[0] >= response_end[0]:
            response_end.popleft()
            traffic -= 1
        else:
            response_start.popleft()
            traffic += 1
            max_traffic = max(traffic, max_traffic)
            
    answer = max_traffic
    return answer