[프로그래머스] 추석트래픽

이런 시간 문제는 모두 초로 바꿔서 생각하는 편이 낫다. 

def solution(lines):
    end_time = []
    start_time = []
    max_value = 0

    for line in lines:
        tmp = line.split(" ")
        h, m, s = map(float, tmp[1].split(":"))
        end_time.append(round(h*60*60+m*60+s, 4))
        start_time.append(round(h*60*60+m*60+s-float(tmp[2][:-1])+0.001, 4))

    for  i in range(len(start_time)):
        st = round(end_time[i], 4)
        et = round(st + 1 - 0.001, 4)
        count = 0
        for j in range(len(start_time)):
            if (start_time[j] <= st and end_time[j] >= st) or (start_time[j] <= st and end_time[j] >= et) or (start_time[j] <= et and end_time[j] >= et) or (start_time[j] >= st and end_time[j] <= et):
                count = count + 1

        if max_value < count:
            max_value = count

    return max_value

각 경우마다 start_time과 end_time을 저장한다.

• end_time은 lines에 주어진 그대로
• start_time은 처리시간 T를 빼주고 0.001초를 더해준 시간

그리고 어떤 구간의 시작(st)은 각 end_time으로 잡는다. 그래야 최대한 많은 트래픽을 포함할 수 있는 상황을 만들 수 있다.

 

그러고 나서, 그 구간에 대한 끝나는 시간(et)을 계산하고(et = st + 1 - 0.001) 각 구간에 속하는 로그의 개수를 구한다.

 

그 구간에 속하려면 네가지 경우가 있다.

 

 

 

1. start_time <= st and end_time >= st

2. start_time <= st and end_time >= et

3. start_time >= st and end_time <= et

4. start_time <= et and end_time >= et

 

 

 

 

이렇게 각 (st, et)마다 네가지 경우에 속하는 로그의 수를 구해주면 된다.

그리고 최댓값 리턴!