2017년 카카오 blind 코딩 테스트 - 추석 트래픽 python

2017년 카카오 blind 코딩 테스트 - 추석 트래픽 python

문제 설명 : 추석 트래픽 추석 트래픽 이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 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 배열에 대해 초당 최대 처리량을 리턴한다.

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

문제 풀이

이번 문제는 트래픽의 시작 시간과 종료 시간을 확인하고, 최대 몇 개가 겹쳐지는 반환하는 문제 입니다.

입력 데이터를 먼저 보면 

[ “2016-09-15 01:00:04.001 2.0s”, “2016-09-15 01:00:07.000 2s”]

문자열 파싱을 통해서 날짜는 떼내고, 종료 시간과 처리된 시간을 분리해서 시작 시간을 구합니다.

자 그리고 트래픽의 시작 시간과 종료 시간을 dictionary에 저장하고선 시작 시간으로 정렬을 합니다.

문제를 풀기 위해서는 state와 history를 만듭니다. state는 트래픽이 동작 중인지를 관리하는 배열이고, 시작 시간에 켜졌고, 종료 시간에 꺼집니다. history는 state를 보고 트래픽이 몇 개가 동작 중인지 보면, 지금 몇 개가 겹쳤구나를 알 수 있겠죠. 그럼 이 history에서 maximum 값을 반환하면 문제는 풀립니다.

[1] 들어오는 배열에서 enumerate를 통해서 index를 받아와 트래픽을 식별합니다. dictionary내에서 시작시간과 종료시간이 어떤 트래픽인지 알게됩니다.

[2] 들어오는 입력을 split을 이용해 공백으로 분리하고 그 중에서 종료 시간(time)과 처리된 시간(duration)을 이용해 시작 시간을 구합니다. 이 때 종료 시간은 시, 분, 초 이므로 split(‘:’)으로 분리하고 초 단위로 계산합니다(60*60*시 + 60*분 + 초). 다음으로 종료 시간에서 처리된 시간을 빼버리면 시작 시간입니다. 

end = int(h) * 60 * 60 + int(m) * 60 + float(n)
duration = float(duration[:-1]) # 뒤에서 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초** 동안 처리된 요청을 의미한다. (처리시간은 시작시간과 끝시간을 포함)

33.020초 - 0.011이면 33.009인데 왠 33.010(?) 

자 그래서 우선 0.001을 더해야지 지문대로 나옵니다.

시작 시간과 종료 시간을 이용해서 시작과 종료되는 시간마다 트래픽이 몇 개가 겹쳐지는 지 확인 할 것 입니다. 그러나 그 순간을 계산하는 것이 아니라, 우리가 원하는 것은 1초 구간의 처리량입니다. 이 1초라는 구간을 생각하면서 코드로 구현하는 것은 복잡합니다. 편하게 시작 시간을 1초가 안되게 늘려주면 되죠.

그래서 최종 시작 시간은 start = end - duration + 0.001 - 0.9991 정도로 줬습니다.

0.999시에는 테스트 케이스 1개(서로 다른 트래픽의 시작과 종료시간이 정확히 겹쳐질때)가 오답이 발생되어 0.0001을 더 주었습니다.

[3] 시작 시간과 종료 시간을 관리하는 dictionary에 키로 넣어주고 트래픽을 식별할 수 있도록 index를 값으로 넣습니다. 

테스트 3의 time_table : {3601.0029000000004: 0, 3604.001: 0, 3604.0019: 1, 3607.0: 1}

0번 트래픽의 시작은 3601 종료는 3604 이구나를 알 수 있죠.

[4] 시간 순대로 정렬을 하기 위해서 sorted()를 사용하여 시간을 가져옵니다.

[5] 가져온 시간대로 state라는 트래픽의 개수만큼 배열을 이용해서 트래픽이 들어온 상태라는 것을 표시합니다.

테스트 케이스 5번에 대해서 state, time, state.count(1) 다음과 같이 나옵니다. 트래픽 10개에 대해서 시작 시간과 종료 시간 2번(*2)에 따라 총 20번이 출력되었죠. 문제 설명에 따라 겹쳐지는 1들이 보이죠? 1을 카운트하면 그 순간 겹쳐지는 트래픽의 개수를 셀 수 있습니다. 

[0, 1, 0, 0, 0, 0, 0, 0, 0, 0] 75596.0539 1

[1, 1, 0, 0, 0, 0, 0, 0, 0, 0] 75596.07190000001 2

[1, 1, 1, 0, 0, 0, 0, 0, 0, 0] 75596.5009 3

[1, 1, 1, 1, 0, 0, 0, 0, 0, 0] 75596.6489 4

[1, 1, 1, 1, 1, 0, 0, 0, 0, 0] 75597.1809 5

[0, 1, 1, 1, 1, 0, 0, 0, 0, 0] 75597.421 4

[0, 1, 1, 1, 1, 0, 0, 1, 0, 0] 75597.43990000001 5

[0, 1, 1, 1, 1, 1, 0, 1, 0, 0] 75597.99990000001 6

[0, 1, 1, 1, 1, 1, 1, 1, 0, 0] 75598.16189999999 7

[0, 0, 1, 1, 1, 1, 1, 1, 0, 0] 75598.233 6

[0, 0, 0, 1, 1, 1, 1, 1, 0, 0] 75598.299 5

[0, 0, 0, 1, 1, 1, 1, 1, 0, 1] 75598.44790000001 6

[0, 0, 0, 0, 1, 1, 1, 1, 0, 1] 75598.688 5

[0, 0, 0, 0, 1, 1, 1, 1, 1, 1] 75599.58690000001 6

[0, 0, 0, 0, 0, 1, 1, 1, 1, 1] 75599.591 5

[0, 0, 0, 0, 0, 0, 1, 1, 1, 1] 75600.464 4

[0, 0, 0, 0, 0, 0, 0, 1, 1, 1] 75600.741 3

[0, 0, 0, 0, 0, 0, 0, 0, 1, 1] 75600.748 2

[0, 0, 0, 0, 0, 0, 0, 0, 0, 1] 75600.966 1

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 75602.066 0

[6] 위의 결과를 트래픽이 겹쳐지는 횟수인 state.count(1)를 history에 저장하고 max(history) 면 정답입니다.

time_table = dict() def duplicated(second):     if second not in time_table.keys():         return second     else:         return dup(second - 0.000001) def solution(lines):     for index, line in enumerate(lines):         date, time, duration = line.split() # 공백으로 분리         h, m, n = time.split(':') # : 시, 분, 초 분리         end = int(h) * 60 * 60 + int(m) * 60 + float(n) # 초로 계산         duration = float(duration[:-1]) # 뒤에 s 제거         start = end - duration + 0.001 - 0.9991                 time_table[duplicated(start)] = index         time_table[duplicated(end)] = index             history = []     state = [0] * len(lines) # 트래픽이 동작 중인지 현재 상태 / 초기화 다 꺼져있다.         for time in sorted(time_table.keys()):         index = time_table[time]         if state[index] == 0: # 트래픽이 시작이면 켠다.             state[index] = 1         elif state[index] == 1: # 트래픽이 종료시간이면 끈다.             state[index] = 0                     history.append(state.count(1)) # 현재 동작 중인 트래픽 개수를 센다.         #print(index, time, state, state.count(1))             return max(history)