문제출처: https://programmers.co.kr/learn/courses/30/lessons/17676
접근법
카카오 공채 코딩테스트 마지막 문제였다.
마지막 문제답게 해설에 제일 어려운 난이도의 문제라고 나와 있었다.
시간 기준으로 구간을 잡는 문제들은 몇 번 봤었는데 시간 단위가 밀리세컨드 단위까지 나와있어서 데이터 전처리를 어떻게 해야 비교를 잘 할 수 있을 지 되게 어려웠다.
-
주어진 시간은 작업이 끝나는 시간이다. (처음에 이 시간을 기준으로 정렬해서 내가 원했던 로직이 구현되지 않았다.)
-
calculate 함수는 끝나는 시간과 처리시간을 이용하여 (시작시간,끝나는시간)을 계산한다. 이는 비교가 가능하게 같은 형식의 시간으로 모두 계산하야 하는데 나는 datetime 라이브러리를 이용하여 hour,minute,second,microsecond으로 나누기 위하여 split 함수를 적절히 활용하여 계산했는데 이것보다 더 효율적인 방법으로 정리해야 할 것 같다.
-
작업이 시작하는 시간 기준으로 정렬한 lines를 반복하여 인덱스에 접근하면 현재 참조하는 로그에서 가장 효율적으로 포함할 수 있는 구간선정은 [시작구간-0.999초,시작구간] 이다.
고려해볼 수 있는 이전 로그들의 형태는 ( 시작구간은 현재 참조하는 로그보다 무조건 작거나 같다! )3-1. 완료시간이 현재 로그의 시작시간보다 작은 경우
-
현재 로그를 포함하고 최대로 포함하려면 1초 구간 설정을 [시작구간-0.999초,시작구간]으로 설정해야 한다.
3-2. 완료시간이 현재 로그의 시작시간보다 크거나 같은 경우
-
이때는 시작시간만 포함하면 모두 포함된다.
3-1의 최적구간은 3-2를 포함한다!
if( w_end >= start - td(microseconds=999000)):
n_arr.append((w_start,w_end))- 만약 현재 참조하는 로그보다 늦게 시작하는 구간을 포함하는 것이 빨리 시작하는 구간을 포함하는 것 보다 더 최적의 정답이라면?
- 만약 k번째 로그가 k+1번째 로그를 포함하는 것이 최적이라면, k+1번째 로그에서의 최적구간에 k번째 로그가 포함된다고 생각한다면 반복문에서 이전 인덱스만 고려해도 된다는 것을 이해할 수 있을 것이다.
코드
from datetime import datetime as dt ,timedelta as td def calculate(lines): for i,l in enumerate(lines): t = l.split(" ")[1].split(":") hour = int(t[0]) minute = int(t[1]) second = int(t[2].split(".")[0]) m_second = int(t[2].split(".")[1]) * 1000 end = dt(2016,9,15,hour,minute,second,m_second) # 0.351s -> 0.351 work_time = l.split(" ")[2].replace("s","") # 0.351 -> 0 second 351000 microseconds work_second = int(work_time.split(".")[0]) work_m_second = 0 if( len(work_time.split(".")) > 1 ): work_m_second = work_time.split(".")[1] work_m_second = int( work_m_second + ( (3-len(work_m_second))*"0" ) ) * 1000 start = end - td(seconds=work_second,microseconds=work_m_second) + td(microseconds=1000) lines[i] = (start,end) return lines def solution(lines): answer = 0 lines = calculate(lines) lines.sort(key=lambda x:x[0]) arr = [] for l in lines: start,end = l[0],l[1] n_arr = [(start,end)] for a in arr: w_start , w_end = a[0],a[1] # 1초 구간 if( w_end >= start - td(microseconds=999000)): n_arr.append((w_start,w_end)) arr = n_arr answer = max(len(arr),answer) return answer
