프로그래머스 광고 삽입 (누적합)

https://school.programmers.co.kr/learn/courses/30/lessons/72414

전체 영상 시간인 파란색 선과, 유저들의 시청 기록인 검은 선들이 주어진다.

위 시청 구간들 사이에 길이가 정해진 공익 광고를 넣는데, 광고 누적 시청 시간이 가장 길도록 넣고, 그 때의 광고 시작 시간을 출력하는 문제이다.

광고의 길이가 정해져 있으므로, 광고 길이를 슬라이더로 생각하며 영상 시간을 기준으로 0초 부터 오른쪽으로 밀어 가는 것이 좋을 것 같다고 생각하였다.

여기서 핵심적인 아이디어는 String 기반 시간을 Int로 변환하여 계산하는 것이라고 생각한다.

영상의 길이 구간은 1초부터 최대 (100시간 - 1초) 만큼이므로, 각 초를 나누어 생각한다면 배열의 크기는 최대 360,000이므로 할 만 하다.

영상 길이를 초로 바꾸고, 0으로 초기화 한 다음 logs 배열을 순회하며 유저들이 본 구간만큼 배열의 값을 증가시킨다.

예를 들면 영상 길이가 100초여서 100 길이의 IntArray를 만든다.
log가 5초~10초였다면, 해당 배열의 인덱스 5~9만큼의 값을 1씩 증가시킨다.
(0초~1초간 본 것은 1초만 본 것이므로, 인덱스 0만 1 증가시키는 것으로 했음)

모든 log값을 순회하며 초당 시청 시간을 모두 구했다면 다음으로 슬라이더를 구상한다.

먼저 0부터 adv_time을 정수로 변환한 값 - 1까지의 구간 합을 구한다.

이후 adv_time부터 영상 시간까지 i번째는 더하고 i-adv_time번째는 빼며 구간합을 구한다.

구간합들 중 현재까지의 값보다 큰 값이 나오면 그 때의 값과 시작 시간을 저장한다.

class Solution {
    fun solution(play_time: String, adv_time: String, logs: Array<String>): String {
        val maxTime = timeToInt(play_time)
        val times = IntArray(maxTime){0}
        val adv_time_int = timeToInt(adv_time)
        for(log in logs){
            val (start, end) = log.split('-')
            val startTimeInt = timeToInt(start)
            val endTimeInt = timeToInt(end)

            for(i in startTimeInt until endTimeInt){
                times[i]++
            }
        }

        var acc = 0L
        var max = 0L
        var maxStart = 0
        for(i in 0 until adv_time_int){
            acc += times[i]
        }
        max = acc

        for(i in adv_time_int until maxTime){
            acc += times[i]
            acc -= times[i - adv_time_int]

            if(max < acc){
                max = acc
                maxStart = i - adv_time_int + 1
            }
        }

        return intToTime(maxStart)
    }

    fun timeToInt(time: String): Int{
        val (h, m, s) = time.split(':').map{it.toInt()}

        return h * 3600 + m * 60 + s
    }

    fun intToTime(int: Int): String{
        val h = int / 3600
        val m = (int - h * 3600) / 60
        val s = int - h * 3600 - m * 60

        return String.format("%02d:%02d:%02d",h,m,s)
    }
}