[프로그래머스] 2021 카카오 블라인드 광고 삽입 - JAVA

문제

광고 삽입

"죠르디"의 동영상 재생시간 길이 play_time, 공익광고의 재생시간 길이 adv_time, 시청자들이 해당 동영상을 재생했던 구간 정보 logs가 매개변수로 주어질 때, 시청자들의 누적 재생시간이 가장 많이 나오는 곳에 공익광고를 삽입하려고 합니다. 이때, 공익광고가 들어갈 시작 시각을 구해서 return 하도록 solution 함수를 완성해주세요. 만약, 시청자들의 누적 재생시간이 가장 많은 곳이 여러 곳이라면, 그 중에서 가장 빠른 시작 시각을 return 하도록 합니다.

풀이

바로 풀이를 떠오르지 못한 문제였다. 구간합이라는 개념을 이 문제를 통해 처음 알게 되었다.

먼저 동영상의 시간을 idx로 가지고 해당 idx에서 동영상의 누적 재생시간을 값으로 가지는 times배열을 선언해준다.

// 동영상 재생시간은 최대 99:59:59이므로 length는 100 * 60 * 60
int[] times = new int[100 * 60 * 60];

시청자들이 해당 동영상을 가장 많이 재생했던 구간을 어떻게 찾을 수 있을까??
logs을 for문을 통해 돌면서 시작시간과 끝시간을 구한후 해당 시간을 idx로 가진 times배열에 +1을 해주면 된다.

for(String log:logs) {
	String[] splitLog = log.split("-");
	int start = getSeconds(splitLog[0]);
	int end = getSeconds(splitLog[1]);
	for(int i=start; i<end; i++) {
		times[i] += 1;
	}
}

이제 어느 부분에 공익광고를 넣을지 찾아야한다.
0부터 play_time까지 for문을 돌면서 adv_time을 이용하여 어느 부분에서 누적 재생 시간이 제일 많은지 찾아주면 된다.

우리가 알아야 하는건 제일 큰 누적 재생 시간을 갖는 곳의 첫 위치이다. 즉, 첫 위치를 옮겨가면서 제일 큰 누적 재생 시간을 갖는 곳을 찾아야 한다.
그러기 위해서는 먼저 adv_time을 통해 시작시간이 0일때 누적 재생 시간을 구해준다.

그림으로 표현하면 다음과 같다.

[0][1][1][1][3]
0~3 누적합 2
1~4 누적합 3
2~5 누적합 5

위를 보고 알 수 있는 사실은 현재 누적 재생 시간은 이전 누적 재생 시간의 첫 재생시간을 빼고 지금 돌고있는 index의 재생시간을 더해주면 된다는 사실이다.
이를 답을 구해주면 된다.

코드

import java.util.*;

class Solution {
    public int getSeconds(String time) {
        return Integer.parseInt(time.substring(0,2)) * 3600
            +  Integer.parseInt(time.substring(3,5)) * 60
            +  Integer.parseInt(time.substring(6,8));
    }
    public String solution(String play_time, String adv_time, String[] logs) {
        String answer = "";
        int totalTime = getSeconds(play_time);
        int[] times = new int[100 * 60 * 60];
        for(String log:logs) {
            String[] splitLog = log.split("-");
            int start = getSeconds(splitLog[0]);
            int end = getSeconds(splitLog[1]);
            for(int i=start; i<end; i++) {
                times[i] += 1;
            }
        }
        
        int advTime = getSeconds(adv_time);
        // 답이될 seconds
        int result = 0;
        // 최대 누적 재생시간의 시작시간 idx
        int removeTimeIdx = 0;
        // 최대 누적 재생시간
        long runingTime = 0;
        for(int i=0; i<advTime; i++)
            runingTime += times[i];
        long prevRuningTime = runingTime;
        for(int i=advTime; i<totalTime; i++) {
            long currRuningTime = prevRuningTime - times[removeTimeIdx] + times[i];
            if(currRuningTime > runingTime) {
                runingTime = currRuningTime;
                result = removeTimeIdx + 1;
            }
            prevRuningTime = currRuningTime;
            removeTimeIdx++;
        }
        int hour = result/3600;
        int min = result % 3600 / 60;
        int seconds = result % 3600 % 60;
        
        answer = String.format("%02d:%02d:%02d", hour,min,seconds);
        return answer;
    }
}