[Python] 프로그래머스 2018 KAKAO 코딩테스트 - 추석 트래픽

문제 설명

추석 트래픽

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

입력 형식

• solution 함수에 전달되는 lines 배열은 N(1 ≦ N ≦ 2,000)개의 로그 문자열로 되어 있으며, 각 로그 문자열마다 요청에 대한 응답완료시간 S와 처리시간 T가 공백으로 구분되어 있다.
• 응답완료시간 S는 작년 추석인 2016년 9월 15일만 포함하여 고정 길이 2016-09-15 hh:mm:ss.sss 형식으로 되어 있다.
• 처리시간 T는 0.1s, 0.312s, 2s 와 같이 최대 소수점 셋째 자리까지 기록하며 뒤에는 초 단위를 의미하는 s로 끝난다.
• 예를 들어, 로그 문자열 2016-09-15 03:10:33.020 0.011s은 2016년 9월 15일 오전 3시 10분 **33.010초**부터 2016년 9월 15일 오전 3시 10분 **33.020초**까지 **0.011초** 동안 처리된 요청을 의미한다. (처리시간은 시작시간과 끝시간을 포함)
• 서버에는 타임아웃이 3초로 적용되어 있기 때문에 처리시간은 0.001 ≦ T ≦ 3.000이다.
• lines 배열은 응답완료시간 S를 기준으로 오름차순 정렬되어 있다.

출력 형식

• solution 함수에서는 로그 데이터 lines 배열에 대해 초당 최대 처리량을 리턴한다.

---

2018 카카오 Blind 개발자 채용 코딩테스트 중 가장 어려웠던 문제였습니다. 아래의 설명은, 문제에 대한 이해를 하셨다는 전제로 설명할 예정입니다.
주어진 로그 데이터를 파싱하고 이를 가공하는 내용입니다. 문제를 이해하기에 앞서, 입력 형식 및 제한 조건에 대해 주의깊게 살펴보아야 합니다.

• line은 S와 T로 구성
• 각 로그는 "고정 길이 2016-09-15 hh:mm:ss.sss 형식"
• 서버의 Timeout 시간은 0.001 ≦ T ≦ 3.000

1번 조건을 통해 문자열 파싱을 진행해야합니다. 우리가 필요한 것은, S와 T입니다.
ex) line : 2016-09-15 01:00:04.002 2.0s

다음과 같은 line 이 주어졌을 때 우리는 "01:00:04.002 2.0s" 이 정보만이 필요합니다. S와 T는 공백을 이용해 구분되어있고, S는 ":" 을 이용해 "시간:분:초" 가 구분됩니다. 이 를 이용해 Python의 split 함수를 이용해 간단히 parsing을 할 수 있습니다. 또한 T는 "s" 가 붙어있기 때문에 이것도 없애주셔야합니다.

파싱 후 구해야할 것은, 각 프로세스 별 "시작시간과 끝나는 시간" 입니다. 1초 단위를 기준으로 처리하는 최대 요청량을 구해야하기에 최초 시간부터 0.001초씩 잘라 끝날때까지 모두 비교하는 방법도 있겠지만, 계산적으로 효율적이지 못합니다. 따라서, 처리 시간의 최소 최대값을 활용해 각 프로세스가 가장 많이 처리되고 있는 "구간" 을 찾을 예정입니다. 
이를 위해서 먼저 Line을 Parsing 하여 각 프로세스 별 시작시간과 끝나는 시간을 구해, 이 값들이 각 구간에 속하는 프로세스인지 확인 할 것입니다. 

카카오 제공 예제 파일

def parsing_line(line):
    _, S,T = line.split(' ')
    time = S.split(':')
    time = list(map(float, time))
    end_time = convert_time_to_second(time)
    ptime = T.split('s')
    ptime = float(ptime[0])
    start_time = end_time - ptime + 0.001
    start_time = round(start_time,3) # 소수점 3자리 반올림
    return start_time, end_time
    
def convert_time_to_second(time): # 시간을 초로 변경
    assert len(time) == 3
    return 3600*time[0] + 60*time[1] + float(time[2])

 

"구간" 을 선택하는 방법은 다음과 같습니다. 각 프로세스 별 끝 시간을 기준으로 + 1초를 "구간" 으로 정의합니다. 
시작 시간이 아닌 끝 시간을 설정한 이유는, 우리가 구해야하는 것은 "최대 처리량" 이며 처리 량은 "시작시간과 끝시간을 포함" 합니다.
따라서, 끝 시간을 포함하는 + 1초 내에 해당하는 프로세스 구간을 구하는 것이 시작 시간을 포함하는 + 1초 구간을 설정하는 것보다 계산적으로 좋습니다. 그 이전 구간은 생각하지 않아도 되니까요.
위 예제 파일에서는 1번 구간은 1번 프로세스의 끝 시간에서 +1초를 한 것입니다. 이 1번 구간에 몇 개의 프로세스가 존재하는지를 전체 프로세스에 대해 체크해보면 됩니다.

N개의 로그가 주어졌을 때, 기준점은 N개가 되고 N개의 구간에 대해 N개의 프로세스들을 체크해보면 됩니다. 이렇게 체크할 경우 $O(n^2)$ 의 시간복잡도를 갖는 알고리즘을 구현 할 수 있습니다. 하지만, 제한 조건 중 최대 T가 3s라는것을 생각해볼 때, 구간의 최대 길이보다 + 3초 이상을 start_time으로 갖는 프로세스는 해당 구간에서 검사할 필요가 없습니다. 이 조건을 통해 알고리즘의 복잡도를 일부 줄일 수 있습니다. 따라서, 이상적인 경우 $O(nlogn)$이 될 수도 있습니다.

def solution(lines):
    length = len(lines)
    max_=1
    max_time = 0
    for i in range(length-1):
        line = lines[i]
        start_time, end_time = parsing_line(line)
        ptime = end_time + 1.0
        count=1
        
        for j in range(i+1, length):
            line = lines[j]
            next_start_time, next_end_time = parsing_line(line)
            if next_end_time  >= ptime + 3.0: # 다음 트래픽의 종료 시간이 3.0s 이상 차이난다면 종료
                break # 이 break문을 통해 알고리즘 속도 개선 가능
            if next_start_time  < ptime:
                count +=1  # 처리량 +1
            max_ = max(max_,count)  # 최대처리량 구하기 
    return max_ # 최대처리량 return