문제 링크

프로그래머스 문제

풀이

크게 생각한 알고리즘은 2개이다.
dp를 이용해 한 시점에 얼마만큼 방송을 하고 있는지 담는다.
그 후 누적합을 통해서 반복하는 경우를 감소시킨다.

function solution(play_time, adv_time, logs) {
    var answer = 0;
    play_time = stringToTime(play_time)
    adv_time = stringToTime(adv_time)
    const timeTable = new Array(play_time).fill(0)
    const dp = new Array(play_time).fill(0)
    
    for(let i=0; i< logs.length; i++){
        let [startTime , endTime] = logs[i].split("-")
        startTime = stringToTime(startTime)
        endTime = stringToTime(endTime)
        for(let cur=startTime+1; cur<=endTime; cur++){ // +1하니까 모두 성공함
            timeTable[cur]+=1 // 이부분을 누적합으로 바꾸니 시간초과 해결
        }
        
    }
    
    for(let i=1; i<=play_time; i++){
        dp[i] = dp[i-1] + timeTable[i]
    }
    
    let curMaxTime = 0;
    
    for(let i=0; i <= play_time - adv_time; i++){
        if(curMaxTime < dp[i+adv_time] - dp[i]){
            curMaxTime = dp[i+adv_time] - dp[i];
            answer = i
        }
    }
    
  
    return timeToString(answer);
}

function stringToTime(string){
    const [hh,mm,ss] = string.split(":").map(v => +v)
    
    return ((hh*60)+mm)*60 + ss
}

function timeToString(num){
    let ss = num%60;
    let restMin = (num - ss)/60;
    if(ss < 10) {
        ss = "0"+ss
    }
    let mm = restMin %60;
    restMin = restMin - mm;
    if(mm < 10) {
        mm = "0"+mm
    }
    let hh = restMin / 60
    if(hh < 10) {
        hh = "0"+hh
    }
    return hh+":"+mm+":"+ss
}

코드

function solution(play_time, adv_time, logs) {
    var answer = 0;
    play_time = stringToTime(play_time)
    adv_time = stringToTime(adv_time)
    const timeTable = new Array(play_time+1).fill(0)
    const dp = new Array(play_time+1).fill(0)
    
    for(let i=0; i< logs.length; i++){
        let [startTime , endTime] = logs[i].split("-")
        startTime = stringToTime(startTime)
        endTime = stringToTime(endTime)
        timeTable[startTime+1]+=1
        timeTable[endTime+1] -=1
        
    }
    
    for(let i=1; i < play_time+1; i++){ // 이 부분을 누적합으로 바꾸어주었다.
        timeTable[i]+=timeTable[i-1]
    }
    for(let i=1; i<=play_time; i++){
        dp[i] = dp[i-1] + timeTable[i]
    }
    
    let curMaxTime = 0;
    
    for(let i=0; i <= play_time - adv_time; i++){
        if(curMaxTime < dp[i+adv_time] - dp[i]){
            curMaxTime = dp[i+adv_time] - dp[i];
            answer = i
        }
    }
    
  
    return timeToString(answer);
}

function stringToTime(string){
    const [hh,mm,ss] = string.split(":").map(v => +v)
    
    return ((hh*60)+mm)*60 + ss
}

function timeToString(num){
    let ss = num%60;
    let restMin = (num - ss)/60;
    if(ss < 10) {
        ss = "0"+ss
    }
    let mm = restMin %60;
    restMin = restMin - mm;
    if(mm < 10) {
        mm = "0"+mm
    }
    let hh = restMin / 60
    if(hh < 10) {
        hh = "0"+hh
    }
    return hh+":"+mm+":"+ss
}