[Python] 추석 트래픽

문제 요약

각 로그에는 요청의 응답 완료 시각과 처리 시간이 주어진다.

모든 요청의 처리 구간을 구한 뒤, 임의의 시점부터 시작하는 1초 구간에 포함되는 요청 수의 최댓값을 반환해야 한다.

요청은 1초 구간 안에서 완료될 필요가 없다. 처리 구간과 1초 구간이 조금이라도 겹치면 해당 요청은 처리량에 포함된다.

핵심 아이디어

모든 시각을 직접 확인할 필요는 없다. 최대 처리량을 만드는 1초 구간은 어떤 요청의 완료 시각에서 시작하도록 잡을 수 있다.

어떤 1초 구간에 여러 요청이 겹친다고 하자. 그 요청들 가운데 가장 먼저 완료되는 요청의 완료 시각까지 구간의 시작점을 오른쪽으로 이동해도 기존 요청은 사라지지 않는다.

• 선택된 요청들은 모두 그 완료 시각 이후에 끝난다.
• 구간의 끝도 함께 오른쪽으로 이동하므로 이후에 시작하는 요청도 제외되지 않는다.

따라서 각 요청의 완료 시각을 1초 구간의 시작점으로 사용해 겹치는 요청 수를 계산하면 충분하다.

밀리초 단위로 변환하는 이유

시간을 float으로 계산하면 소수 표현 오차 때문에 구간의 경계에서 잘못된 결과가 나올 수 있다.

문제의 시간 정밀도는 밀리초이므로 모든 시각을 정수 밀리초로 변환한다.

01:02:03.456
= 1시간 + 2분 + 3초 + 456밀리초
= ((1 × 60 + 2) × 60 + 3) × 1000 + 456

처리 시간도 문자열을 직접 분리하여 밀리초 정수로 만든다.

요청의 시작 시각 계산

완료 시각을 end, 처리 시간을 duration이라고 하면 요청의 시작 시각은 다음과 같다.

start = end - duration + 1

처리 시간은 시작 시각과 완료 시각을 모두 포함하기 때문에 1ms를 더해야 한다.

예를 들어 완료 시각이 1000ms이고 처리 시간이 1ms라면 처리 구간은 [1000, 1000]이어야 한다.

start = 1000 - 1 + 1 = 1000

1초 구간과 요청이 겹치는 조건

1초 구간의 시작 시각을 window_start라고 하면 밀리초 단위의 구간은 다음과 같다.

[window_start, window_start + 999]

요청의 처리 구간 [start, end]가 이 구간과 겹치려면 다음 두 조건을 모두 만족해야 한다.

end >= window_start
start <= window_start + 999

각 후보 완료 시각에 대해 모든 요청을 확인하면서 이 조건을 만족하는 요청의 개수를 센다.

풀이 과정

1. 각 로그에서 완료 시각과 처리 시간을 분리한다.
2. 완료 시각과 처리 시간을 정수 밀리초로 변환한다.
3. start = end - duration + 1로 처리 시작 시각을 계산한다.
4. 모든 요청의 [start, end] 구간을 저장한다.
5. 각 요청의 완료 시각에서 시작하는 1초 구간을 만든다.
6. 해당 1초 구간과 겹치는 요청의 수를 계산한다.
7. 계산된 요청 수 중 최댓값을 반환한다.

Python 코드

def solution(lines):
    intervals = []

    def to_milliseconds(time_text):
        hour, minute, second_text = time_text.split(":")
        second, millisecond = second_text.split(".")

        return (
            (int(hour) * 60 * 60 + int(minute) * 60 + int(second))
            * 1000
            + int(millisecond)
        )

    def duration_to_milliseconds(duration_text):
        number = duration_text[:-1]  # 마지막 's' 제거

        if "." not in number:
            return int(number) * 1000

        second, millisecond = number.split(".")
        millisecond = millisecond.ljust(3, "0")

        return int(second) * 1000 + int(millisecond)

    for line in lines:
        _, time_text, duration_text = line.split()

        end = to_milliseconds(time_text)
        duration = duration_to_milliseconds(duration_text)
        start = end - duration + 1

        intervals.append((start, end))

    max_throughput = 0

    for _, window_start in intervals:
        window_end = window_start + 999
        throughput = 0

        for start, end in intervals:
            if end >= window_start and start <= window_end:
                throughput += 1

        max_throughput = max(max_throughput, throughput)

    return max_throughput

코드 설명

완료 시각 변환

to_milliseconds()는 hh:mm:ss.sss 형식의 시각을 자정부터 지난 밀리초로 변환한다.

모든 로그가 같은 날짜에 속하므로 날짜는 계산에 사용할 필요가 없다.

처리 시간 변환

duration_to_milliseconds()는 마지막의 s를 제거한 뒤 정수부와 소수부를 분리한다.

소수부는 최대 세 자리이므로 ljust(3, "0")을 사용해 밀리초 세 자리로 맞춘다.

0.1s   -> 100ms
0.12s  -> 120ms
0.123s -> 123ms
2s     -> 2000ms

구간 겹침 검사

두 닫힌 구간이 겹치지 않는 경우는 다음 두 가지다.

• 요청이 1초 구간보다 먼저 끝난다.
• 요청이 1초 구간보다 나중에 시작한다.

이를 반대로 표현하면 코드의 겹침 조건이 된다.

if end >= window_start and start <= window_end:

정확성

각 로그의 완료 시각과 처리 시간을 밀리초 정수로 변환하고, 양 끝을 포함한다는 조건에 따라 정확한 처리 구간 [start, end]를 구한다.

임의의 최대 처리량 구간에 포함된 요청 중 가장 먼저 완료되는 요청의 완료 시각까지 구간 시작점을 이동해도 포함된 요청 수는 줄어들지 않는다. 따라서 적어도 하나의 최대 처리량 구간은 어떤 요청의 완료 시각에서 시작한다.

알고리즘은 모든 요청의 완료 시각을 후보로 검사하며, 각 후보에서 정확한 구간 겹침 조건을 만족하는 요청을 모두 센다. 그러므로 계산된 최댓값은 가능한 모든 1초 구간의 최대 처리량과 같다.

시간 복잡도

로그의 개수를 N이라고 하면, N개의 완료 시각마다 모든 요청 N개를 확인한다.

O(N^2)

N은 최대 2,000이므로 약 400만 번의 구간 비교로 충분히 처리할 수 있다.

공간 복잡도

각 요청의 시작 시각과 완료 시각을 저장하므로 공간 복잡도는 다음과 같다.

O(N)

주의할 점

• 처리 시간은 시작 시각과 완료 시각을 모두 포함하므로 시작 시각 계산에 +1ms가 필요하다.
• 1초 구간도 양 끝을 포함하므로 [시작, 시작 + 999ms]로 계산한다.
• 부동소수점 연산을 사용하면 경계값 비교에서 오차가 발생할 수 있으므로 정수 밀리초를 사용한다.
• 요청이 1초 구간 안에서 시작하거나 끝나지 않더라도 두 구간이 일부라도 겹치면 처리량에 포함한다.

정리

이 문제는 로그의 처리 시간을 정확한 닫힌 구간으로 변환한 뒤, 1초 구간과 겹치는 요청의 최댓값을 구하는 문제다.

모든 시간을 정수 밀리초로 변환하고 요청의 완료 시각만 후보로 검사하면, 경계값 오류 없이 O(N^2)에 해결할 수 있다.