◾ 추석 트래픽 : 프로그래머스 LEVEL 3
문제
이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 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 배열에 대해 초당 최대 처리량을 리턴한다.
입출력 예
| 입력 | 출력 |
|---|---|
| ["2016-09-15 01:00:04.001 2.0s","2016-09-15 01:00:07.000 2s"] | 1 |
| ["2016-09-15 01:00:04.002 2.0s","2016-09-15 01:00:07.000 2s"] | 2 |
| ["2016-09-15 20:59:57.421 0.351s","2016-09-15 20:59:58.233 1.181s","2016-09-15 20:59:58.299 0.8s","2016-09-15 20:59:58.688 1.041s","2016-09-15 20:59:59.591 1.412s","2016-09-15 21:00:00.464 1.466s","2016-09-15 21:00:00.741 1.581s","2016-09-15 21:00:00.748 2.31s","2016-09-15 21:00:00.966 0.381s","2016-09-15 21:00:02.066 2.62s"] | 7 |
◾ 풀이
1. 해설
- 그리디 알고리즘을 이용하여 해결하였다.
- 로그가 응답완료시간을 기준으로 오름차순 정렬되어 있기 때문에 각 응답완료시간을 기준으로 가능한 최대 처리량을 확인한다.
- 로그 완료 시간 및 처리시간은 초단위까지 있으며 초는 소수점 3자리까지 존재한다.
- float형의 경우 값을 처리하는 도중 오류가 발생할 수 있으므로 값에 1000을 곱해 int형으로 만들어준다.
- 각 종료 시간을 기준으로 최대 처리량을 계산한다.
- 아래 두 경우일 때 최대 처리량을 +1 한다.
- 다음 로그의 시작 시간이 종료 시간 이전
- 다음 로그의 시작 시간이 (현재 종료 시간 + 1초) 이전
- 각 최대 처리량 중 최대값을 선택해나간다.
- 아래 두 경우일 때 최대 처리량을 +1 한다.
2. 프로그램
- 로그 분리(응답 완료 시간(날짜, 시간), 처리 시간)
- 시작 시간, 종료 시간 초 단위, int형으로 변형(* 1000)
- 각 종료 시간 기준 최대 처리량 계산
- 아래 두 경우일 때 최대 처리량을 +1 한다.
- 다음 로그의 시작 시간이 종료 시간 이전
- 다음 로그의 시작 시간이 (현재 종료 시간 + 1초) 이전
- 아래 두 경우일 때 최대 처리량을 +1 한다.
- 각 최대 처리량 중 최대값 선택
# 코드
def solution(lines):
answer = 0
# 날짜는 모두 같으므로 삭제
lines = [each.split(' ')[1:] for each in lines]
# (시작 시간, 종료 시간) 형태로 변경
timeTable = []
for end, t in lines:
# 시간은 초로 변환한 값에 1000을 곱해준다.
# float형으로 소수점 3자리까지 사용하는 경우 값이 이상하게 들어가는 경우가 생겨서
# 1000을 곱해 int형으로 사용한다.
end = list(map(float, end.split(':')))
end = int((end[0] * 3600 + end[1] * 60 + end[2]) * 1000)
start = end - int(float(t[:-1])* 1000) + 1
timeTable.append((start, end))
print(timeTable)
len_timeTable = len(timeTable)
# 각 로그의 종료 시간을 기준으로 가능한 모든 경우 탐색
# 각 경우 중 최대값을 답으로 반환
for idx, (start, end) in enumerate(timeTable):
cnt = 1
end_p1 = end + 999
for j in range(idx+1, len_timeTable+1):
if j == len_timeTable:
break
# 다음 시간대의 로그 시작 시간이 현재 종료 시간 이하이거나 1초 미만의 차이인경우
# 최대 처리량 + 1
if end >= timeTable[j][0] or end_p1 >= timeTable[j][0]:
cnt += 1
answer = cnt if cnt > answer else answer
return answer
후라이드 치킨