프로그래머스 Lv3 추석 트래픽

2018 KAKAO BLIND RECRUITMENT 문제이다.

 

문제 풀이

1. 먼저 주어진 시간을 시작시간과 종료시간으로 적절히 연산가능하도록 변환해 준다.(저는 datetime 라이브러리를 사용하였습니다.)

2. 각 시작시간과 종료시간마다 1초의 여유를 두고 동시에 진행중인 프로세스의 개수를 센다.

자세한 풀이는 카카오 공식 풀이를 참조하세요.

* 계속 테스트케이스의 한 두개가 틀렸는데, 종료시간에 대해서만 비교를해서 그랬습니다. 시작시간과 종료시간 모두 동시에 수행중인 프로세스의 수가 바뀔 수 있습니다.

* 과정 2 부분을 이중포문으로 구현했으므로 시간복잡도는 O(n^2)이 됩니다.

 

Python Code

import datetime
from collections import deque
 
def solution(lines):
    answer = 0
    traffics = []
    
    for l in lines:
        date, time, t = l.split()
        tmp_date = list(map(int,date.split("-")))
        tmp_time = time.split(":")
        sec, msec = tmp_time[2].split('.')
        end = datetime.datetime(tmp_date[0],tmp_date[1],tmp_date[2],int(tmp_time[0]),int(tmp_time[1]),int(sec),int(float("0."+msec)*1000000))
        start = end - datetime.timedelta(seconds = float(t[:-1])) + datetime.timedelta(seconds = 0.001)
        
        traffics.append((start,end + datetime.timedelta(seconds = 1)))
    #기준 시간    
    for start, end in traffics:
        count_start = 0
        count_end = 0
        for s,e in traffics:
            if s < start <= e :
                count_start += 1
            if s < end <= e :
                count_end += 1
        if max(count_start,count_end) > answer :
            answer = max(count_start,count_end)
        
    return answer

Line 8 - 16 : 주어진 시간을 datetime 라이브러리를 활용하여 연산 가능하게 변환하고 traffics 리스트에 넣어줍니다.

Line 18 - 27 : 첫 for문의 start와 end가 기준시간으로 해당 시간의 1초 여유 안에 있는 traffics의 요소의 개수를 세어줍니다.

 

문제 링크

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