[Swift][프로그래머스][그리디] 추석 트래픽

요구능력

그리디

 

문제풀이

임의시간부터 1초간 처리하는 요청의 최대 개수를 구해야한다.

오름차순 정렬까지 되어있기 때문에 우리가 원하는 시간에서부터 1초만 탐색하면 되니까 그리디로 풀게되었다.

 

1) 처리시간은 시작시간과 끝시간을 포함한다.

우리가 구해야할 것은 시작시간과 끝시간으로 정해졌다.

처음에 주어지는 시간이 끝시간이다.

시간을 비교해야 될 때는 가장 작은 단위에 맞춰서 비교하는게 가장좋다.

모두 우선 초단위로 바꾸고 더한다음 1000을 곱해서 밀리초를 만들어주고 밀리초를 더해주면 시간양식이 우선 완성된다.

끝시간을 저장하는 배열 endTime에 추가해준다.

 

그리고 시작시간을 구하려면 지속시간을 빼주면 된다.

하지만, 그냥 빼주면 안되고 문제에서 아래와 같이 되어있으니 1을 더해줘야한다.

 

2) 끝시간을 기준으로 한 비교

시작시간의 경우에는 지속시간에 따라서 정렬의 형태가 달라져있을 수 있다.

끝시간을 기준으로 비교를 해보면서 정답을 구하면 되는데,

시작시간의 비교값을 i부터 시작하는 이유는 i이하는 그 이전의 시작시간이므로 비교할 필요가 없다.

그리고 endTime[i] >= startTime[j] - 1000 이 안되고, endTime[i] > startTime[j] - 1000 이어야 되는 이유는 위에 문제사진을 보면 이해가 되겠지만, 1000을 그대로 뺀것까지 포함하게되면 01:00:02.002 ~ 01:00:04.002가 되서 문제에서 정의하는 초단위를 넘어가게된다.

 

후기

꽤나 까다로운 문제

 

코드

func solution(_ lines:[String]) -> Int {
    var startTime = [Int]()
    var endTime = [Int]()
    var result = 0
    for i in lines{
        var sp = i.split(separator: " ").map{String($0)}//문자열 분해
        let time = sp[1].split(separator: ":") //시간 문자열 분해
        let hour = Int(time[0])! * 3600 //시간 -> 초
        let min = Int(time[1])! * 60 //분 -> 초
        
        let secTime = time[2].split(separator: ".").map{Int(String($0))!} //초와 밀리초 분해
        let sec = secTime[0] //초
        let miliSec = secTime[1] //밀리초
        
        let obtain = (hour + min + sec) * 1000 + miliSec //밀리초로 변경한 시간값
        
        endTime.append(obtain)
        sp[2].removeLast() //2.0s와 같이 되어있어서 s를 제거.
        
        let duration = Int(Double(sp[2])! * 1000) //시작 시간을 구하기위해 지속시간을 구함
        startTime.append(obtain - duration + 1) //끝시간 - 지속시간 + 1
    }
    for i in 0..<lines.count{
        var cnt = 0
        for j in stride(from: i, to: lines.count, by: 1){
            if endTime[i] > startTime[j] - 1000{
                cnt += 1
            }
        }
        result = max(result, cnt)
    }
    return result
}