2021 카카오 코테 문제 - 광고삽입 [Kotlin]

2021 카카오 코드 테스트의 5번 문제 광고 삽입 대한 풀이입니다.

 

문제에 대한 설명과 풀이는 kakao Tech에서 확인할 수 있으며, 이 포스트에서는 kotlin으로 문제를 해결하는 방법을 작성하겠습니다.

입력값

• play_time:String = 동영상의 총길이를 "HH:MM:SS" 형식으로 나타낸 문자열
• adv_time:String  = 광고 영상의 총길이를 "HH:MM:SS" 형식으로 나타낸 문자열
• logs:Array<String> = 시청자들의 누적 재생시간을 "HH:MM:SS-HH:MM:SS" 형식으로 나타낸 배열

출력 결과

• answer:String = 광고 영상 삽입 시 최고 누적 재생시간의 시작시간을 "HH:MM:SS" 형식으로 나타낸 문자열

설명

광고 영상을 어느 시간에 삽입해야 시청자의 누적 재생시간이 가장 많을지 계산하는 문제입니다.

우선 입력값에 대한 제약사항을 확인해보면 다음과 같습니다.

• play_time: 00시간 00분 01초 이상 99시간 59분 59초
• adv_time: 00시간 00분 01초 이상 play_time과 같거나 작다.

정답을 계산하기 위해 logs의 누적 재생시간의 각 중복되는 시간을 계산해야 합니다.

 

예시

4명의 시청자의 기록을 표로 그려보았습니다.

맨 위 index는 초를 의미하며, 즉 영상의 총길이는 10초를 의미합니다.

• a : 00:00:01 ~ 00:00:04
• b : 00:00:02 ~ 00:00:06
• c : 00:00:08 ~ 00:00:09
• d : 00:00:01 ~ 00:00:09

누적 재생 시간표

여기서 헷갈리면 안 되는 점은 재생 시간의 끝은 종료를 의미하므로, 재생시간에 포함해서는 안됩니다.

4번을 예시로 보면 a의 재생시간이 종료되므로 값에서 제외되었습니다.

 

이렇게 영상의 누적 재생 시간은 초 단위로 계산을 해두면 어느 시간이 가장 적게 재생되었는지, 또는 가장 많이 재생되었는지 알 수 있게 됩니다.

 

초 단위 변환

위의 방식대로 풀이하기 위해 입력값인 HH:MM:SS 형식을 Int 값으로 변경시킬 수 있도록 함수를 만들어줍니다.

//HH:MM:SS를 초로 변경하여 반환
fun ConvertSecond(strTime:String):Int {
    val (t, m, s) = ConvertTime(strTime)
    return time2Second(t, m, s)
}

//HH:MM:SS를 split하여 반환
fun ConvertTime(strTime:String):Triple<Int,Int,Int> {
    val sl = strTime.split(":")
    return Triple(sl[0].toInt(), sl[1].toInt(), sl[2].toInt())
}

//시, 분, 초를 초 단위로 변경
fun time2Second(time:Int, minute:Int, second:Int):Int {
    return (time * 60 * 60) + (minute * 60) + (second)
}

 

그 후 play_time과 adv_time을 초로 변환해줍니다.

fun solution (play_time:String, adv_time:String, logs:Array<String>):String {
    var answer = ""
    var play_time_sec = ConvertSecond(play_time)
    var adv_time_sec = ConvertSecond(adv_time)
    
    retrun answer
}

 

Logs 추출

시청자들의 누적 재생시간을 계산하기 위해 logs의 요소를 초로 변환하고 이를 기록해주려 합니다.

fun solution (play_time:String, adv_time:String, logs:Array<String>):String {
    var answer = ""
    var play_time_sec = ConvertSecond(play_time)
    var adv_time_sec = ConvertSecond(adv_time)
    
    for( i in logs.indices) {
        var splitList = logs.get(i).split("-")
    	var log_start_time_sec = ConvertSecond(splitList[0])
        var log_end_time_end = ConvertSecond(splitList[1])
    }
    
    retrun answer
}

 

누적 재생 수 계산

각 시청자의 시작 재생시간과 종료 재생시간을 얻었다면, 각 시간별(초 단위)로 몇 명의 시청자가 재생하였는지 알아야 합니다.

위에서 설명한 시청자 재생 시간표와 같이 초 단위로 계산하기 위해선 초 단위로 몇 명의 시청자가 동영상을 재생 중인지에 대한 정보를 기록할 배열이 필요합니다.

배열의 크기는 동영상의 총길이 + 1 만큼 주어지면 되므로 Array<Int>(play_time_sec + 1) { 0 } 이 됩니다.

• 영상의 최대 길이는 99시간 59분 59초 
• 배열의 최대 크기는 (99 * 60 * 60) + (59 * 60) + 59 = 35999입니다.
• + 1이 주어지는 건 index와 시간을 동일하게 만들기 위함입니다.

기록할 배열을 만들었다면 이제 기록을 해야 합니다.

배열에 기록될 정보는 시청자의 재생시간 ~ 종료 시간이 돼야 하므로, 시작 시간과 종료 시간의 범위에 값을 주어야겠지만, 각 log 별 시간차만큼 반복 횟수가 늘어나므로 비효율적이므로 다른 방법으로 접근하겠습니다.

 

1. 시작 시간과 종료 시간의 index에 +1 , -1을 기록합니다.
2. arr[index] = arr[index] + arr[index - 1]을 반복하여 계산합니다.
   1. 입력값 조건이 1초부터 이므로 index는 1부터 시작합니다.

재생횟수표

Code

fun solution (play_time:String, adv_time:String, logs:Array<String>):String {
    var answer = ""
    var play_time_sec = ConvertSecond(play_time)
    var adv_time_sec = ConvertSecond(adv_time)
    
    var arrCache = Array<Int>(play_time_sec + 1) { 0 } // 입력값 조건 0이 없으므로, 값을 1증가
    
    for( i in logs.indices) {
        var splitList = logs.get(i).split("-")
    	var log_start_time_sec = ConvertSecond(splitList[0])
        var log_end_time_end = ConvertSecond(splitList[1])
        
        arrCache.set(log_start_time_sec, arrCache.get(log_start_time_sec) + 1)//시작 index 1삽입
        arrCache.set(log_end_time_sec, arrCache.get(log_end_time_sec) - 1) // 시작 index -1 삽입
    }
    
    for(i in 1..play_time_sec) {
        arrCache.set(i, arrCache.get(i) + arrCache.get(i - 1))
    }
    
    retrun answer
}

 

광고 삽입 위치 계산

누적 수 까지 계산이 완료되었다면 어느 위치에 광고를 두어야 효과적일지 계산되면 끝입니다!

1. 누적 시간 계산을 위해 arrCahce에서 1 ~ adv_time_sec 범위만큼의 값을 합쳐 maxPlayTime과 temp 변수에 저장 및 index를 기록할 maxPlayIndex 변수를 선언합니다.
   
   1. maxPlayIndex는 광고가 삽입되기 적합한 시작시간 즉 answer입니다.
   2. maxPlayTime, temp, maxPlayIndex 타입은 Long으로 지정해야 문제를 통과할 수 있습니다.
2. arrCache에서 adv_time_sec ~ play_time_sec 범위를 1씩 이동합니다. (index)
3. 이동하며 arrCache.get(index) - arrCache.get(index - adv_time_sec)를 계산합니다.(sum_adv)
   1. 이를 통해 index 이동 후 누적 시간이 증가되었는지 감소되었는지 알 수 있습니다.
4. sum_adv + maxPlayTime 값을 temp와 비교합니다.
   1. maxPlayTime 값이 클 경우 현재 누적 광고시간 값이 가장 큰 것이므로 temp에 값을 저장하고 현재 index를 ㅡmaxPlayIndex에 저장합니다.
5. 1~4 과정을 반복 후 나온 maxPlayIndex를 HH:MM:SS 형식으로 변경하면 정답입니다!

Code

    fun solution(play_time: String, adv_time: String, logs: Array<String>): String {
        val play_time_sec = ConvertSecond(play_time)
        val adv_time_sec = ConvertSecond(adv_time)
        val arrCache:Array<Long> = Array<Long>(play_time_sec + 1) { 0 }
       
        ...
        
        var maxPlayTime:Long = 0
        var maxPlayIndex:Long = 0
        var temp:Long = 0
        // adv_time_sec 범위의 값을 계산
        for(i in 1 until adv_time_sec) {
            maxPlayTime += arrCache.get(i)
        }
        
        temp = maxPlayTime
        
        //동영상의 끝은 입력값 조건 상 0이므로 계산하지 않습니다. (until)
        for(i in adv_time until play_time_sec) {
            maxPlayTime = maxPlayTime + arrCache.get(i) - arrCache.get(i - adv_time)
            if (maxPlayTime > temp) {
                temp = maxPlayTime
                maxPlayIndex = i - adv_time_sec + 1
            }
        }
        var answer = String.format("%02d:%02d:%02d", maxPlayIndex / 3600, maxPlayIndex / 60 % 60, maxPlayIndex % 60)
        return answer
}

---

Source Code

fun solution(play_time: String, adv_time: String, logs: Array<String>): String {
    val play_time_sec = ConvertSecond(play_time)
    val adv_time_sec = ConvertSecond(adv_time)
    var arrCache = Array<Int>(play_time_sec + 1) { 0 } // 입력값 조건 0이 없으므로, 값을 1증가
    
    for( i in logs.indices) {
        var splitList = logs.get(i).split("-")
    	var log_start_time_sec = ConvertSecond(splitList[0])
        var log_end_time_end = ConvertSecond(splitList[1])
        
        arrCache.set(log_start_time_sec, arrCache.get(log_start_time_sec) + 1)//시작 index 1삽입
        arrCache.set(log_end_time_sec, arrCache.get(log_end_time_sec) - 1) // 시작 index -1 삽입
    }
    
    for(i in 1..play_time_sec) {
        arrCache.set(i, arrCache.get(i) + arrCache.get(i - 1))
    }
    
    var maxPlayTime:Long = 0
    var maxPlayIndex:Long = 0
    var temp:Long = 0
    // adv_time_sec 범위의 값을 계산
    for(i in 1 until adv_time_sec) {
        maxPlayTime += arrCache.get(i)
    }
        
    temp = maxPlayTime

    //동영상의 끝은 입력값 조건 상 0이므로 계산하지 않습니다. (until)
    for(i in adv_time until play_time_sec) {
        maxPlayTime = maxPlayTime + arrCache.get(i) - arrCache.get(i - adv_time)
        if (maxPlayTime > temp) {
            temp = maxPlayTime
            maxPlayIndex = i - adv_time_sec + 1
        }
    }
    
    var answer = String.format("%02d:%02d:%02d", maxPlayIndex / 3600, maxPlayIndex / 60 % 60, maxPlayIndex % 60)
    return answer
}