iyOmSd/Title: Algorithm풀이

[Swift Algorithm] 프로그래머스 17676 추석 트래픽 (2018 카카오 블라인드)

냄수 2020. 11. 18. 13:49
반응형

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

 

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

입력: [ 2016-09-15 20:59:57.421 0.351s, 2016-09-15 20:59:58.233 1.181s, 2016-09-15 20:59:58.299 0.8s, 2016-09-15 20:59:58.688 1.041s, 2016-09-15 20:59:59.591 1.412s, 2016-09-15 21:00:00.464 1.466s, 2016-09-15 21:00:00.741 1.581s, 2016-09-15 21:00:00.748

programmers.co.kr

 

풀이방법

처음에 문제를 잘못이해해서 잘못풀엇어요...

주어진입력은 완료된 시각이였어요..

시작시간인줄알고...

 

아무튼...!

 

문자열 파싱을 통해서 초 분 시를 구분해서 처리시간을 빼서 시작시간과 종료시간을 구하는 방식으로 하려다 보니 너무 복잡해 보였어요

이방법보다는 전체를 ms단위로 통일해서 구하는게 편하더라구요

 

그리고 중요한게

입력이 종료되는 시간순으로 정렬 되어있다는 거에요

이를 이용해서 겹치는 시간을 체크해서 최대 트래픽을 찾을 수 있어요

무슨 뜻이냐면

종료순으로 정렬되어있기때문에 하나씩 비교할 때

다음 element의 종료시간은는 현재 비교하는 종료시간보다 늦게 끝남을 보장받아요

따라서 현재 비교하는 종료시간 + 1000ms(1초) 보다 시작시간이 더 빠르다면

그 element는 겹치는 시간안에 실행중이라는 뜻이죠

 

 

그림으로 보면

종료되는 시점이 정렬되어있음을 이용하면

현재비교중(찐보라색)인 로그의 끝시간 + 1000ms(1초) 사이에 있는 트래픽의 갯수를 파악하면서

최대 트래픽인 경우를 찾으면돼요

위의 그림과같이 현재비교중인 ( 로그의 끝시간 + 1초)시간보다 시작시간이 빠르다면

해당 구간 안에서 트래픽이 실행되는거에요

왜 시작지점만 파악하냐면

종료되는 지점은 무조건 현재비교중인 로그보다 늦게 될거니까 뒤에있을거고 시작지점만 비교하는거죠

 

 

 

private func solutionP17676(_ lines:[String]) -> Int {
    
    var process: [LogData] = []
    
    for line in lines {
        let split = line.components(separatedBy: .whitespaces)
        let dates = split[0].components(separatedBy: "-")
        let year = dates[0]
        let month = dates[1]
        let day = dates[2]
        let time = split[1].components(separatedBy: ":")
        let hour = time[0]
        let min = time[1]
        let sec = time[2]
        let data = LogData(year: year,
                           month: month,
                           day: day,
                           hour: hour,
                           min: min,
                           sec: sec,
                           excute: split[2])
        process.append(data)
    }
    
    var maxCount = 0
    for i in 0..<process.count {
        var count = 1
        let end = process[i].endTime
        for j in i+1..<process.count {
            if process[j].startTime < end + 1000 {
                count += 1
            }
        }
        maxCount = max(count, maxCount)
    }
    
//    print(maxCount)
    return maxCount
}

struct LogData {
    let year: String
    let month: String
    let day: String
    let hour: String
    let min: String
    let sec: String
    var excute: String
    
    var endTime: Double {
        let mhourF = Double(hour)! * 60 * 60 * 1000
        let mminF = Double(min)! * 60 * 1000
        let msecF = Double(sec)! * 1000
        return mhourF + mminF + msecF
    }
    
    var startTime: Double {
        let mhourF = Double(hour)! * 60 * 60 * 1000
        let mminF = Double(min)! * 60 * 1000
        let msecF = Double(sec)! * 1000
        var temp = excute
        temp.removeLast()
        let mExcuteF = Double(temp)! * 1000 - 1
        let mTotal = mhourF + mminF + msecF
        return Double(mTotal - mExcuteF)
    }
}
반응형