23.03.01 파이썬 코딩 퀴즈#177 추석 트래픽(프로그래머스 스쿨)

이번 문제는 추석 트래픽 문제이다.

일단 설명이 굉장히 길고 어려워 보인다. 천천히 하나씩 풀어가 보자.

 

1. 초당 최대 처리량

응답 완료 여부와 관계없이 임의 시간부터 1초간 처리하는 요청의 개수를 의미한다.

2. line 배열은 N개의 로그 문자열로 되어 있으며, 각 로그 문자열마다 요청에 대한 응답완료시간 S 와 처리시간 T가 공백으로 구분되어 있다.  S 기준으로 오름차순 정렬되어 있다.

S 는 2016-09-15 는 고정값으로 존재하고 뒤에 hh:mm:ss.sss 형식으로 되어 있다.

T 는 0.1s, 0.312s 처럼 소수점 셋째 자리까지 기록하며 뒤에 s로 끝난다.

3. 서버에는 타임아웃이 3초로 적용되어 있기 때문에 처리시간은 0.001 <= T <= 3.000 이다.

 

이제 위 조건을 바탕으로 lines 배열에 대해 초당 최대 처리량을 계산해야 한다.

입출력 예제2번을 확인해보면 좀 더 문제를 이해하는데 도움이 된다.

날짜는 동일하기 때문에 생략하고

먼저 첫 번째 로그 01:00:04.002 응답완료 시간이고 처리에는 2.0초가 소요되었다. 따라서 실제 처리에 걸린 시간은 01:00:02.003~01:00:04.002 가 된다

두 번째 로그 01:00:07.000 은 역시 처리에 2초가 소요되었다. 따라서 실제 처리에 걸린 시간은 01:00:05.001~01:00:07.000 이다.

두 로그가 겹치는 시간은 없다. 하지만 구간을 1초로 설정해서 확인해보면 04.002 ~ 05.001 까지의 1초 구간에 정확히 두 로그가 겹치게 된다. 따라서 초당 최대 처리량은 2개가 된다.

 

즉 로그 전체를 나열하고, 구간을 1초 단위로 설정해서 로그가 몇 개가 처리되는지를 확인해야 한다.

내가 작성한 코드는 위와 같다.

먼저 반복문을 통해 전달받은 lines를 초 단위로 계산한 [시작시간, 끝나는 시간] 배열을 time_table에 전달하고

해당 time_table을 다시 반복문으로 돌며 확인하게 된다.

이 때, 확인해야 할 값은 기준이 되는 time_table[i]의 끝나는 값과 나머지 요소들의 시작시간을 비교하여 1초 안에 몇개가 존재하는지 확인하는 것이다.

확인해야 하는 구간은 1초 이지만, 이를 0.001초를 기준으로 나누어서 다 확인하는 순간 시간 제한에 또 걸린다.

1초를 구간으로 나눌때 효율적으로 나눌 수 있는 구간이 바로 각 로그의 끝나는 시점이기 때문에, 각 로그의 끝나는 시간을 다른 로그의 시작 시간과 비교하면 쉽게 해결 가능하다.

 

해당 코드로 모든 테케를 통과 하였는데, 개인적으로 다시 한번 코드를 손보다가 문제점을 발견했다.

코드를 작성하면서도 마음에 걸렸던 부분인데 바로 float()으로 처리한 부분이다.

float()으로 처리한 ss 값에 다시 float(t)를 빼주고, 다시 0.001을 뺐는데, 그 결과가 이상하게 나왔다.

float(ss) 와 float(ss)-0.001 한 결과값

mm 단위에 맞춰서 변환했더니 코드가 굉장히 길어지고 보기불편해졌다.

 

아 그리고 해당 lines는 끝나는 시간을 기준으로 오름차순 정렬되어 있다.

따라서 끝나기 이전 시간의 로그들과의 비교는 불필요하다. 

위 입출력 예제 3번을 그래프로 나타낸 것인데, 해당 그래프를 보면 왜 비교가 불피요한지 확인 가능하다.