[코딩테스트] 프로그래머스 - [1차]추석 트래픽(2018 Kakao) (Lv.3) in Python

"2016-09-15 hh:mm:ss.sss #.###s"로 주어지는 문자열의 집합이 매개변수로 주어질 때,

최대 초당 처리량을 반환하여라.

 

상당히 긴 문제다! 자세한 설명은 여기로 ↓

- programmers.co.kr/learn/courses/30/lessons/17676 

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

 

풀이

- 일단 들어오는 입력을 잘 가공시켜줘야 겠다.

2016-09-15 hh:mm:ss.sss #.###s

부분을, 로그의 시작시간과 끝나는시간으로 나눠 각각 배열에 넣어주자.

 

- 시작시간 (startTimes)과 끝나는 시간(endTimes) 배열에서 굳이 (#번째 로그의 시작시간 - #번째 로그의 끝나는 시간) 으로 짝지어 줄 필요가 없는데,

임의의 시간 t에서,

처리되고 있는 총 로그의 수는,

(t보다 이전에 시작된 로그의 수) - (t보다 이전에 끝난 로그 수)이기 때문이다.

 

- 위의 정보를 가공할 때 중요한 점은,

실수 계산을 피할 수 있도록 가공해주는 점이다.

모두 알다시피 실수를 이용한 정확한 계산은 컴퓨터에서 불가능하기 때문에,

0.00...0001의 오차로두 오류가 날 수 있다.

 

따라서 hh * 60 * 60 + mm * 60 * ss.sss 으로 시간을 초로 변환한 후, 전체에 1000을 곱해줘

정수를 이용한 연산을 할 수 있도록 하자.

 

- 총 처리량을 살펴보는 시간을 언제로 할 지가 문제였는데,

문제에서 제공한 그림을 뚫어져라 보니  (⊙_⊙) 처리량의 변화는 어떠한 로그의 시작 시간 혹은 끝나는 시간마다 변하는 것을 볼 수 있었다.  (⊙∇⊙)

따라서 어떠한 로그의 시작/끝나는 시간부터 1초동안의 처리량을  살펴보도록  결정한다!  

 

파이썬 구현

def solution(lines):
answer = 0
    count = 0

    # pre-processing
    startTimes = []
    endTimes = []

    for x in lines:
        a, time, duration = x.split()
        hh, mm, ss = time.split(":")

        endTime = (int(hh)*60*60 + int(mm)*60)*1000 + (float(ss))*1000
        startTime = endTime - float(duration[:-1])*1000 + 1 # Note1

        endTimes.append(endTime)
        startTimes.append(startTime)

    endTimes.sort() # Note 2
    startTimes.sort()

    n = len(lines)
    i,j = 0,0
    while i < n:
        count = 0
        # Note 3
        if startTimes[i] <= endTimes[j]:
            curTime = startTimes[i]
            i += 1
        else:
            curTime = endTimes[j]
            j += 1

        # Note 4
        for t in startTimes:
            if t <= curTime + 1*1000 - 1:
                count += 1

        for t in endTimes:
            if t < curTime:
                count -= 1

        answer = max(answer, count) # Note 5
    
    return answer

 

 

Note 1

- 소요시간은 로그 시작과 끝 시간을 모두 포함하기에, 0.001초를 더해줘야 했다. 따라서 0.001*1000인 1을 더해줌

 

Note 2

- 앞에서부터 하나 하나 살펴보므로 endTimes와 startTimes배열 모두 오름차순으로 정렬

 

Note 3

- startTimes와 endTimes에서 아직 탐색을 하지 않은 요소들 중, 최소를 curTime (현재시간)으로 설정

 

Note 4

- 현재 시간보다 이전에 시작한 작업은 +1로 카운트, 현재 시간보다 전에 끝난 작업은 -1로 카운트

 

Note 5

- 각 시간마다 처리량이 기존 결과값보다 크면 결과값 갱신