17676

날짜: 2022년 3월 8일 오후 3:41

코드

Algorithm/17676.py at main · Junroot/Algorithm

풀이

2가지 문제를 해결해야 됐다.

1. 로그를 기반으로 처리시각의 시작 시각과 끝 시각 구하기
2. 초당 최대 처리량 구하기

처리시각 구하기

ms 단위로 처리해야되기 때문에 2016-09-15에서 몇 ms가 지났는지를 기준으로 처리하기로 했다. 로그의 마지막 부분인 처리시간 T를 ms단위로 변환하는 것에 어려움이 있었는데, 로그에 적혀있는 숫자 개수를 기반으로 처리했다. 숫자의 개수가 0이 될 때까지 뒤에 0을 더 붙이는 형식으로 구현했다.

def second_to_ms(second):
    result = 0
    digit_count = 0
    for c in second:
        if "0" <= c <= "9":
            result = result * 10 + int(c)
            digit_count += 1
    while digit_count < 4:
        result *= 10
        digit_count += 1
    return result

초당 최대 처리량 구하기

처음에는 0ms부터 24 * 60 * 60 * 1000ms 까지 모든 경우를 다 구하려고했는데 이 방법은 당연히 시간 초과가 발생했다.

초당 최대 처리량은 어떤 한 처리의 마지막 ms 구간을 포함하는 1초간의 범위에 항상 최대값이 나온다는 것을 알게되어 이를 이용했다. 현재 로그의 최종 응답 시간부터 1초 간에 포함되는 처리량을 구하기 위해서는 아래의 두 조건을 만족하면 된다.

1. (현재 로그의 최종 응답 시각부터 1초 뒤) > (요청이 들어온 시각)
2. (현재 로그의 응답 시각) < (응답 시각)

현재 입력값이 응답 시각으로 정렬되어있으므로 현재 로그이후의 로그들을 확인하면서 1번 조건만 확인하면 된다.