프로그래머스 2018 KAKAO BLIND RECRUITMENT 코딩테스트에서 출제된 문제
추석 트래픽 문제
분석
트래픽의 시작 시간과 끝 시간을 구하고 1초 사이에 가장 많은 트래픽이 있는 순간의 개수가 답이 된다.
그리디 알고리즘을 활용하여 풀면 될 것같아 시도하였다.
1.시간 계산
트래픽이 끝나는 시간과 끝날 때까지 걸린 시간이 주어지는데 이를 통해서 트래픽이 시작하는 시간과 트래픽이 끝나고 1초가 지난 시점을 구해준다.
원래 초,분,시 계산할때 '120초=2분'이 되어서
minute += second//2 second -= second%60위와 같은 방식이 되어야 하지만 문제에서 서버 타임아웃이 3초 = s가 3을 넘기지 않으므로 단순히 뺄셈 작업으로도 가능하다.
시작 시간을 구할 때는 끝나는 시간에 걸린 시간을 빼주고
트래픽이 끝나고 1초가 지난 시점은 끝나는 시간에 1초를 더해주면 된다.
그렇게 계산이 끝나면 [시작 시간, 끝난 시간+1]형태로 times 리스트에 append 해준다.
2.트래픽 최대 개수 구하기
[끝난 시간+1]을 기준으로 times 리스트를 정렬한다.
그 후에 이중 반복으로 times 시간을 하나씩 비교해준다. 0번째 시간을 기준으로 하면 1번째부터 n번째까지 3번째 시간을 기준으로 하면 4번째부터 n번째까지 비교를 해준다.
기준 시간의 [끝난 시간+1]이 비교하는 시간의 [시작 시간]보다 크다면 카운트를 하나씩 올려준다. [끝난 시간+1] 기준으로 정렬하였기 때문에 시작 시간이 더 앞에 있다면 범위 내에 포함되는 것이다.
3.소수점 문제
두가지 케이스가 있다
CASE1: ["2016-09-15 01:00:04.001 2.0s", "2016-09-15 01:00:07.000 2s"]
CASE2: ["2016-09-15 01:00:04.002 2.0s", "2016-09-15 01:00:07.000 2s"]
case1의 경우에 1이고 case2의 경우에 2가 답이 된다. 이 겹치는 부분이 float 변수의 계산으로 문제가 생기는 경우가 있어서 1초뒤의 시간을 0.999초 뒤의 시간으로 변경해주었다.
코드
def goTime(time, s): # ①
time[2]+=s
if time[2]>=60:
time[2]-=60
time[1]+=1
elif time[2]<0:
time[2]+=60
time[1]-=1
if time[1]>=60:
time[1]-=60
time[0]+=1
elif time[1]<0:
time[1]+=60
time[0]-=1
return time
def solution(lines):
times, answer = [], 0
for i in lines: ①
time=i[11:23].split(':')
sTime= goTime([int(time[0]),int(time[1]),float(time[2])], -float(i[24:-1]))
eTime = goTime([int(time[0]),int(time[1]),float(time[2])], 0.999) # ③
times.append([sTime, eTime])
times.sort(key=lambda x: (x[1],x[0])) # ②
for i in range(len(times)): ②
tmp = 0
for j in range(i,len(times)):
if times[i][1]>times[j][0]: tmp+=1
answer=max(answer, tmp)
return answer