[프로그래머스] 광고 삽입

문제

프로그래머스

입력

모든 시간 형태 = "HH:MM:SS"

play_time: String = 종료 시간 (총 재생 시간)
adv_time: String = 광고 시간
logs: [String] = [startTime-endTime, ....] // 각 유저 별 시청 구간 (1 <= logs 길이 <= 300,000)

여기서 startTime 이상 endTime 미만이 각 log의 구간이다.

결과

result: String = "HH:MM:SS"

가장 많은 유저가 보는 시간 중 광고 삽입될 시간
단 조건을 만족하는 구간이 여러 군대면 시작시간이 가장 빠른 시간으로 한다.

해석

이 문제는 솔직히 카데고리 분류를 끝내하지 못했고 힌트를 조금 보면서 풀었다.

먼저 말하면 이 문제는 누적합 문제다.

 

어디서 납득을 했냐면 재생구간은 연속적인 시간 형태라는 점을 생각해보면 누적합쪽도 번뜩할 수 있다.

 

1. HH:MM:SS 의 시간 형식이 존재하므로 계산을 할 때는 편하게 초로 바꾸는 함수가 필요

2. 반대로 초를 HH:MM:SS으로 바꾸는 함수 필요

3. 여기서 누적합에 재료는 특정 구간에 시청중인 시청자수이다.

4. 각 log마다 구간을 표시해한다 이때 startTime은 포함하고 endTime은 포함하면 안되므로 1, -1로 표시한다.

5. 이후 각 구간의 누적합을 표시한다.

6. 전체 play_time의 누적합을 구한다.

7. 가장 많은 시청자 수와 함께 해당 시간을 기록한다.

 

t = 특정 시간 
최대 시청자수 = 누적시정차수[t] - 누적시청자수[t-advTime]
가장 효율적인 광고 시작 시간 = t - 광고 시간 길이 + 1 , +1인 이유는 시작시간을 포함해야하므로 

 

코드

import Foundation

func strToInt(_ s: String) -> Int {
    let componets = s.components(separatedBy: ":")
    let h = Int(componets[0])!
    let m = Int(componets[1])!
    let s = Int(componets[2])!
    
    return h*3600 + m*60 + s 
}

func intToStr(_ t: Int) -> String {
    var t = t 
    let h = t / 3600
    t %= 3600
    let m = t / 60
    t %= 60
    let s = t 
    
    let hStr = h < 10 ? "0\(h)" : "\(h)"
    let mStr = m < 10 ? "0\(m)" : "\(m)"
    let sStr = s < 10 ? "0\(s)" : "\(s)"

    return hStr + ":" +  mStr + ":" + sStr
}


func solution(_ play_time:String, _ adv_time:String, _ logs:[String]) -> String {
    
    let endTime = strToInt(play_time)
    let advTime = strToInt(adv_time)
    var accTime: [Int] = [Int](repeating:0, count:endTime+1)
    
    if endTime == advTime {
        return "00:00:00"
    }
    
    let logs = logs.map{$0.components(separatedBy:"-")}.map{
        return (strToInt($0[0]), strToInt($0[1]))
    }
    
    // 각 log마다 start와 end 표시 
    for log in logs {
    
        let s = log.0
        let e = log.1
        
        accTime[s] += 1
        accTime[e] -= 1

    }
    
    // 각 구간의 누적합 구함
    for t in 1...endTime {
        accTime[t] += accTime[t-1]
    }
    
    // 전체 플레이 시간의 누적합 구함 
    for t in 1...endTime {
        accTime[t] += accTime[t-1]
    }
    
    var mostView: Int = 0 // 최대 시청자 수
    var answer: Int = 0 // 광고 시작 시간 
    
    // 시작은 광고 시작바로 직전부터 끝까지 순회한다.
    for t in stride(from: advTime-1, to: endTime, by: 1) {
        
        if t >= advTime {
            
            if mostView < accTime[t] - accTime[t-advTime] {
                mostView = accTime[t] - accTime[t-advTime]
                answer = t - advTime + 1 
            }
            
        } else {
            if mostView < accTime[t] { 
                mostView = accTime[t] 
                answer = t - advTime + 1
            }
        }
        
    }
        
    return intToStr(answer)
}