문제

Programmers Lv3, 광고 삽입

핵심

• 시청자들의 누적 재생 시간이 가장 많은 곳에 공익 광고가 들어갈 시작 시간을 구해야 한다. 동영상 재생 길이, 공익 광고 재생 길이, 시청자들이 동영상을 재생했던 구간 정보가 주어진다.
• 크게 다음 단계로 문제에 접근할 수 있다.
  1. 시간(HH:MM:SS) 초로 변환하기
  2. 시청자들이 동영상을 가장 많이 재생한 구간 찾기
  3. 누적 재생 시간이 가장 많은 시작 시간(초) 다시 시간(HH:MM:SS)으로 변환하기
• 먼저 12:22:07 형식으로 시간이 주어지므로, 누적 재생 횟수가 가장 많은 시간을 구하기 위해 시간을 초로 변환해야 한다.

int convertSecond(String time) {
	String[] parts = time.split(":");
	int hours = Integer.parseInt(parts[0]);
	int minutes = Integer.parseInt(parts[1]);
	int seconds = Integer.parseInt(parts[2]);
	return hours * 3600 + minutes * 60 + seconds;
}

• 누적 재생 횟수가 가장 많은 구간을 찾았다면, 다시 문제에서 원하는 시간 형식으로 변환해야 한다.

String convertTime(long seconds) {
	long hours = seconds / 3600;
	seconds %= 3600;
	long minutes = seconds / 60;
	seconds %= 60;
	return String.format("%02d:%02d:%02d", hours, minutes, seconds);
}

• 문제의 핵심은 시청자들이 동상을 가장 많이 재생한 구간을 찾는 것이다. 가장 간단한 방법은 재생 시간 만큼 배열을 선언하고, 사용자가 시청한 구간은 +1을 하는 것이다.

for (var log : logs) {
	String[] times = log.split("-");
	int start = convertSecond(times[0]);
	int end = convertSecond(times[1]);
	for (int i = start; i < end && end <= play; ++i) {
    	runnings[i]++;
	}
} 

• runnings의 값은 해당 시점의 시청자 수를 의미한다. 그렇다면, 이제 특정 시점에 광고했을 때 가장 많이 시청한 구간을 찾을 수 있다.

for (int i = 0; i + ad <= play; i++) {
	long viewCnt = 0;
	for (int j = i; j < i + ad; j++) {
		viewCnt += runnings[j];
	}
	if (maxView < viewCnt) {
		maxView = viewCnt;
		ans = i;
	}
}

• 0초부터 시작하여 광고 시작 시간 동안의 조회수 합계를 구한다. 조회수 합계가 가장 큰 광고 시작 시간을 시간 형식으로 변환하면 정답이 된다!
  
• 그런데 아쉽게도 실제 제출을 해보면 시간 초과가 된다. 플레이 시간이 99시간 99분 99초일 때 대략 36만초가 된다. 광고 재생시간도 이와 같으므로 360,000 * 360,000 은 100억이 넘는 값이므로 시간 내에 계산하기 위해선 다른 방법이 필요하다!

구간 합 적용하기

• 구간 합을 적용해 보자. 먼저, 특정 시점의 시청자 수를 가지고 누적 조회수를 구할 수 있다.

for (int i = 1; i <= play; i++) runnings[i] += runnings[i - 1];

• 특정 시점의 누적 조회수를 알고 있으면, 매번 특정 구간의 조회수를 계산할 필요 없다. 예를 들어 3초 ~ 5초 사이의 조회수를 구하고 싶다면 5초까지의 누적 조회수 - 3초까지의 누적 조회수로 $O(1)$에 구할 수 있다.

for (int i = 0; i + ad <= play; i++) {
	long viewCnt = (i == 0) ? runnings[i + ad - 1] : runnings[i + ad - 1] - runnings[i - 1];         
	if (maxView < viewCnt) {
		maxView = viewCnt;
		ans = i;
	}
}

• 누적 조회수를 구하여 시간을 단축했지만 여전히 특정 구간의 시청자 수를 구하는 것은 $O(N^2)$에 동작한다. 사용자가 시청한 구간을 구간 합으로 상수에 처리할 수 있다. 핵심 아이디어는 시작 값과 끝값 두 개를 표시한다. 한 번의 반복문을 통해 구간 합(누적 시청자)을 구하면 된다.

// 3 ~ 5초 시청했다면 (5초는 시청 종료 시간)
{0, 0, 0, 1, 0, -1} -> {0, 0, 0, 1, 1, -1}
// 2 ~ 4초 시청했다면
{0, 0, 1, 0, -1} -> {0, 0, 1, 1, 0}

• 코드로 나타내면 아래와 같다.

for (var log : logs) {
	String[] times = log.split("-");
	int start = convertSecond(times[0]);
	int end = convertSecond(times[1]);
	runnings[start]++;                // 범위만 표시
	if (end < play) runnings[end]--;  // 범위만 표시
}
// 구간 시청자 수 표시
for (int i = 1; i <= play; i++) runnings[i] += runnings[i - 1];

// 누적 시청자 수 표시
for (int i = 1; i <= play; i++) runnings[i] += runnings[i - 1];

개선

시간복잡도

• $O(playing)$

코드

import java.util.*;

class Solution {
    public String solution(String play_time, String adv_time, String[] logs) {
        
        int play = convertSecond(play_time);
        int ad = convertSecond(adv_time);
        
        long[] runnings = new long[play + 1];
        
        for (var log : logs) {
            String[] times = log.split("-");
            int start = convertSecond(times[0]);
            int end = convertSecond(times[1]);
            runnings[start]++;
            if (end < play) runnings[end]--;
        }
        
        for (int i = 1; i <= play; i++) runnings[i] += runnings[i - 1];
        
        for (int i = 1; i <= play; i++) runnings[i] += runnings[i - 1];
        
        long maxView = 0;
        long ans = 0;        
        for (int i = 0; i + ad <= play; i++) {
            long viewCnt = (i == 0) ? runnings[i + ad - 1] : runnings[i + ad - 1] - runnings[i - 1];         
            if (maxView < viewCnt) {
                maxView = viewCnt;
                ans = i;
            }
        }
        return convertTime(ans);
    }
    
    int convertSecond(String time) {
        String[] parts = time.split(":");
        int hours = Integer.parseInt(parts[0]);
        int minutes = Integer.parseInt(parts[1]);
        int seconds = Integer.parseInt(parts[2]);
        return hours * 3600 + minutes * 60 + seconds;
    }
    
    String convertTime(long seconds) {
        long hours = seconds / 3600;
        seconds %= 3600;
        long minutes = seconds / 60;
        seconds %= 60;
        return String.format("%02d:%02d:%02d", hours, minutes, seconds);
    }
}