문제 설명
이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 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 배열에 대해 초당 최대 처리량을 리턴한다.
입출력 예제
예제1
- 입력: [ "2016-09-15 01:00:04.001 2.0s", "2016-09-15 01:00:07.000 2s" ]
- 출력: 1
예제2
- 입력: [ "2016-09-15 01:00:04.002 2.0s", "2016-09-15 01:00:07.000 2s" ]
- 출력: 2
- 설명: 처리시간은 시작시간과 끝시간을 포함하므로 첫 번째 로그는 01:00:02.003 ~ 01:00:04.002에서 2초 동안 처리되었으며, 두 번째 로그는 01:00:05.001 ~ 01:00:07.000에서 2초 동안 처리된다. 따라서, 첫 번째 로그가 끝나는 시점과 두 번째 로그가 시작하는 시점의 구간인 01:00:04.002 ~ 01:00:05.001 1초 동안 최대 2개가 된다.
예제3
- 입력: [ "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초 각 구간의 처리량을 구해보면 (1)은 4개, (2)는 7개, (3)는 2개임을 알 수 있다. 따라서 초당 최대 처리량은 7이 되며, 동일한 최대 처리량을 갖는 1초 구간은 여러 개 존재할 수 있으므로 이 문제에서는 구간이 아닌 개수만 출력한다.
문제풀이
처음 생각은 응답이 오는 처음 시간부터 시작해서 마지막 응답이 끝나는 시간까지 1ms 씩 반복문을 돌리려고 했다. 이건 정말 비효율적인 생각이었다. 카카오에서 알려준 해설을 보고나니 응답이 오고 가는 순간에만 갯수를 계산하는 아이디어를 얻을 수 있었다.
def cnt(ti, ti_li):
c = 0
start = ti
end = ti + 1000
for i in ti_li:
if i[1] >= start and i[0] < end:
c += 1
return c
def solution(lines):
answer = 0
if len(lines) == 1:
return 1
time_line = []
for time in lines:
date, times, second = time.split()
times=times.split(':')
second = float(second.replace('s',''))*1000
end = (int(times[0])*3600+int(times[1])*60+float(times[2]))*1000
start = end - second + 1
time_line.append([start,end])
max_count = 1
for t in time_line: # time_line에 저장된 순간들만 탐색
max_count = max(max_count, cnt(t[0], time_line), cnt(t[1], time_line))
answer = max_count
return answer
split(), replace()함수를 이용해서 시간을 int로 바꾼뒤 소숫점뒤를 정수로 만들어서 더하기 위해 1000을 곱했다. 그 뒤 응답수를 계산하여 max_count를 구했습니다.
function solution(lines) {
var answer = 0;
if (lines.length === 1){
return 1
}
let time_line = []
for (let i = 0;i<lines.length; i++){
const arr = lines[i].split(" ")
const times = arr[1].split(':')
const second = parseFloat(arr[2].replace('s',''))*1000
let end = (parseInt(times[0])*3600+parseInt(times[1])*60+parseFloat(times[2]))*1000
let start = end - second + 1
console.log(start, end)
time_line.push([start,end])
}
let max_count = 1
function count(ti, ti_li){
let c = 0
let start = ti
let end = ti + 1000
for (let i=0; i<ti_li.length; i++){
if (ti_li[i][1] >= start && ti_li[i][0] < end){
c += 1
}
}
return c
}
for (let i = 0 ; i<time_line.length; i++){
max_count = Math.max(max_count, count(time_line[i][0], time_line), count(time_line[i][1], time_line))
}
answer = max_count
return answer;
}
'Algorithm' 카테고리의 다른 글
[PROGRAMMERS] 야근 지수 - heap (0) | 2021.07.26 |
---|---|
[PROGRAMMERS] 입국심사 (0) | 2021.07.22 |
[BAEKJOON] 3085 사탕 게임 (0) | 2021.07.16 |
[Programmers] 가장 먼 노드 (0) | 2021.07.15 |