249. 2018 KAKAO BLIND RECRUITMENT [1차] 추석 트래픽
1) 어떤 전략(알고리즘)으로 해결?
2) 코딩 설명
<내 풀이>
# 초당 최대 처리량은 요청의 응답 완료 여부에
# 관계없이 임의 시간부터 1초(=1,000밀리초)간
# 처리하는 요청의 최대 개수
def solution(lines):
answer = 0
lis = []
cnt = 0
for line in lines :
date, time, inter = line.split()
inter = float("".join(list(inter)[0:len(inter)-1]))
h,m,n = map(float, time.split(":"))
endtime = h*3600 + m*60 + n
starttime = endtime - inter + 0.001
lis.append((starttime, endtime ))
# lines 배열은 응답완료시간 S를 기준으로 오름차순 정렬
# lis 에 담긴 순서도 응답완료 시간 오름차순임
# < 구간 겹침 로직 >
# 임의의 시간에서 1000밀리초 구간에서
# 쿼리가 존재하기만 하더라도 처리된 것으로 처리하기 때문에,
# 단순히 겹치는 것만 확인하여 겹친다면 카운트를 1 증가
# lis[인덱스][0] = 시작시간, lis[인덱스][1] = 종료시간
for l in range(len(lis)) :
# l 은 검사중인 아이 (나랑 겹치는 애들 누구누구있냐 ~ )
cnt = 0 # 검사중인 아이랑 겹치는 횟수
for k in range(l , len(lis)) :
# 시작시간[k]를 1 초 앞으로 당겼을 때,
# 종료시간[l]보다 작다면 1초 내에 처리된 것
if lis[l][1] > lis[k][0]-1 :
cnt+=1
# 기존 있던 최대 겹침 횟수랑 비교했을 때보다 크면
# 걔가 answer로 갱신
answer = max(answer, cnt)
return answer
< 내 틀렸던 풀이, 문제점>
일단 시작시간, 끝시간은 구했즤
# 초당 최대 처리량은 요청의 응답 완료 여부에
# 관계없이 임의 시간부터 1초(=1,000밀리초)간
# 처리하는 요청의 최대 개수
def solution(lines):
answer = 0
dict = {}
for line in lines :
date, time, inter = line.split()
inter = float("".join(list(inter)[0:len(inter)-1]))
h,m,n = map(float, time.split(":"))
endtime = h*3600 + m*60 + n
starttime = endtime - inter + 0.001
return answer
- 그러나 난관들이 존재하지
- 원래 나는 걍 일초단위로 끊는 것인줄 알았지.
- 그러나 문제에서는
이렇게도 일초의 간격으로 치는 것이지 이게 맞아?
- 이걸 일초로 허용해주더라 이것이지~ .. 참
3) start_time 배열과 end_time 배열의 요소들을 순회하며 대소를 비교한다. 이때 end_time 배열의 요소들은 정렬되어 있음을 보장받기 때문에, end_time 배열을 기준으로 대소를 비교한다.
주어진 구간에서 최대, 최소를 구하는 방법은 여러가지가 있지만, 이 문제에서는 임의의 시간에서 1000밀리초 구간에서 쿼리가 존재하기만 하더라도 처리된 것으로 처리하기 때문에, 단순히 겹치는 것만 확인하여 겹친다면 카운트를 1 증가시키면 된다. 1000 밀리초 떨어진 것을 어떻게 처리하면 좋을까?
start_time[j]를 1000 밀리초 앞으로 당겼을 때, end_time[i]보다 작다면 1000 밀리초 내에 처리된 것으로 생각할 수 있다.
이 때, 주의해야 할 점은 조건이 end_time[i] <= start_time[j] - 1000이 아닌, end_time[i] < start_time[j] - 1000라는 것이다.
처리시간은 시작시간과 끝 시간을 모두 포함하기 때문에, 끝시간에서 생각한다면 999 밀리초 이내에 같은 작업이 끝남과 동시에 시작된다면 초당 처리시간이 증가하게 되는것이다. 따라서 start_time[j] - 1000이라면 end_time[i]보다 작아야 초당 처리시간이 증가하게 된다.
