[Swift / Python] 프로그래머스(Lv3) - [1차] 추석 트래픽 (2018 KAKAO BLIND RECRUITMENT)

안녕하세요 :)

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

풀이

먼저 0.001s(밀리세컨드, msec)를 1로 갖는 단위로 변환해줍니다.
몇 초인지를 구한다음 1000을 곱해주면 msec이 됩니다.

로그 문자열 2016-09-15 03:10:33.020 0.011s은 
"2016년 9월 15일 오전 3시 10분 33.010초"부터 
"2016년 9월 15일 오전 3시 10분 33.020초"까지 
"0.011초" 동안 처리된 요청을 의미한다.

1. 문제에서 위와 같이 설명을 했으므로, 요청이 시작된 시간 start는 앞에 시간과 분을 생략하고 대략 살펴보면
   33020msec - 11msec + 1msec = 33010msec 입니다.
2. 이렇게 start 배열을 만들어 주면 end 배열도 만들어줘야하는데
   end는 요청이완료된시간 msec + 1000msec(1초) 입니다.
   1초를 더해주는 이유는 33.010초에 요청이 완료됐다면 34.010까지 1초동안 해당 요청이 있는 것으로 쳐지기 때문입니다. (초당 처리량을 구하기 때문에)
3. start 배열을 오름차순으로 정렬합니다. (end는 문제에서 이미 오름차순 정렬되어있는거에다 1000msec 을 더한거니까 그대로 사용)
4. 투포인터(startIdx, endIdx)를 이용해서 start가 end 보다 작다면 포함되어 있는 경우이니까 traffic을 1씩 증가시킵니다.
   start가 end보다 크거나 같다면 포함되는 경우가 아니므로 traffic을 감소시키고, endIdx를 증가시킵니다.

Swift 코드입니다. Swift로 풀때 Float로 하면 오차가 납니다 ❗️
Double로 해주면 답은 제대로 나오나.. 좀 더 정확하게 하려면 Decimal을 이용해야 될 것 같습니다.

import Foundation

func solution(_ lines:[String]) -> Int {
    var starts = [Int]()
    var ends = [Int]()
    
    for line in lines {
        let time = line.components(separatedBy: [" ", ":", "s"])
        let msec = (Int(time[1])! * 3600 + Int(time[2])! * 60) * 1000 + Int(Double(time[3])! * 1000)
        let start = msec - Int(Double(time[4])! * 1000) + 1
        let end = msec + 1000
        starts.append(start)
        ends.append(end)
    }
    
    starts.sort()
    var startIdx = 0
    var endIdx = 0
    var traffic = 0
    var maxTraffic = 0
    let n = lines.count
    
    while startIdx < n && endIdx < n {
        if starts[startIdx] < ends[endIdx] {
            traffic += 1
            maxTraffic = max(traffic, maxTraffic)
            startIdx += 1
        } else {
            traffic -= 1
            endIdx += 1
        }
    }
    
    return maxTraffic
}

Python 코드입니다.

def solution(lines):
    starts = []
    ends = []

    for line in lines:
        line = line.split()
        time = line[1].split(':')
        msec = int((int(time[0]) * 3600 + int(time[1]) * 60 + float(time[2])) * 1000)
        start = msec - int(float(line[2][:-1]) * 1000) + 1
        end = msec + 1000
        starts.append(start)
        ends.append(end)
    
    starts.sort()
    traffic = 0
    max_traffic = 0
    start_idx = 0
    end_idx = 0
    n = len(lines)
    
    while start_idx < n and end_idx < n:
        if starts[start_idx] < ends[end_idx]:
            traffic += 1
            max_traffic = max(traffic, max_traffic)
            start_idx += 1
        else:
            traffic -= 1
            end_idx += 1
        
    return max_traffic