[algorithm] 2018 Kakao Blind Recruitment 1차 - 추석 트래픽

1. 문제분석

https://programmers.co.kr/learn/courses/30/lessons/17676

코딩테스트 연습 - [1차] 추석 트래픽

처음 이 문제를 봤던 건 몇달 전이었는데 그 때는 파싱만 해놓고 date 처리나 시간처리를 어떻게 해야할지 몰라서 못풀었었다.

 

그런데 이번에 다시 풀이 할 때는 생각보다 쉽게 풀었다. 

- 구간을 모두 볼 필요는 없고 로그 개수만큼만 보면 된다.

    ㄴ end time  ~ end time +0.999초

 

즉 아래와 같이 로그가 들어올 때

S1 T1

S2 T2

S3 T3

 

이런식으로 데이터를 정리할 수 있을 것이다.

종료시각(s)	수행시간(s)	시작시각(s)
S1	T1	S1-T1+0.001
S2	T2	S2-T2+0.001
S3	T3	S3-T3+0.001

종료시각은 빠른순서대로 정렬되어있다.

그러면 우리가 확인해야할 것은

S1~S1+0.999s  구간에  S2~ 이후의 시작시간이 포함되는 개수 를 카운팅 하면된다.

이렇게 로그 개수만큼 확인하면 초당 최대 처리량을 구할 수 있다.

 

- 어차피 시간은 로그의 endtime 기준으로 측정할 것이기 때문에 date는 신경 쓸 필요 없다.

   (전날에 들어온 요청이 오늘 끝난경우는 고려할 필요 없다.)

 

 

2. 풀이

def solution(lines):
    End=[]
    Start = []
    for line in lines:
        date,time,t = line.split()
        tsplit = list(map(float,time.split(":")[::-1])) 
        endtime=0.0
        for i in range(3):
            endtime+=tsplit[i]*(60**i)
        starttime = endtime*1000-float(t[:-1])*1000+1
        End.append(endtime*1000)
        Start.append(starttime)
    maxsolve=0
    for i in range(len(End)):
        result=0
        for j in range(i,len(End)):
            if End[i]+999 >= Start[j]:
                result+=1
        if result>maxsolve:
            maxsolve=result
    return maxsolve

먼저 입력을 받아서 endtime을 연산하기 쉽도록 초단위로 바꿔주었다.

처음에는 초 단위로 float 끼리 연산을 했는데 일부 테스트케이스에서 부동소수점 연산 오류로 인해 값이 이상하게 나와서 다시 *1000을 곱해서 int 연산으로 했더니 오류가 없었다.

 

 

3.algorithm

1ms 단위로 모든 윈도우를 슬라이딩 윈도우로 풀면 당연히 풀 수 없는 문제였다.

카카오 공식 풀이에도 나왔지만 실제로 값이 변하는 순간은 각 로그의 시작/끝점 뿐이라는 것을 알면 O(N^2) 풀이로 풀 수 있었다. 슬라이딩 윈도우를 사용하지 않고 O(n log n) 으로 풀 수 있는 방법도 있다는데 잘 떠오르지는 않는다.