[프로그래머스] 광고 삽입 - Java

문제 링크

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

문제 설명

링크 참조

제한사항

링크 참조

알고리즘: 누적합

풀이

시청자들의 누적 재생 시간이 가장 많이 나오는 곳을 찾는 것이 목표다.

먼저 초마다 몇 명이 시청 중인지를 구해야 한다. -> 누적합을 이용
시작 시각과 종료 시각만 알면 O(n)으로 구할 수 있다.

ex) 시작 시각 0초, 종료 시각 3초 (종료 시각이 3초면 0~2초까지 시청)
그러면 view[0] += 1, view[3] += -1 -> 왜냐하면 view를 누적합 했을 때 0초부터 2초까지는 시청했기 때문에 1값이 유효해야함 3초부터는 시청을 종료했기 때문에 -1로 1값을 없애줘야 한다.
[1, 0, -1] sum_view[0] => 1, sum_view[1] => 1, sum_view[2] => 0

위 방식을 이용해서 초마다 몇 명이 시청했는지 알 수 있는 sum_view(코드에선 view로 통일)를 구하고, sum_view를 이용해서 시청 시간의 누적합을 구하면 된다. -> sum_view의 누적합을 이용

시청 시간의 누적합인 cmt_sum을 구했다면, 구간에 누적 시청 시간을 구할 수 있다.
ex) 10초 ~ 150초의 누적 시청 시간은 cmt_sum[150] - cmt_sum[10-1]이다.

이제 구간에 누적 시청 시간을 구할 수 있으니, 모든 플레이 구간을 완전 탐색하면 된다.

소스 코드

import java.util.*;
class Solution {
    static int[] view = new int[100*60*60 + 1];
    static long[] cmt_sum = new long[100*60*60 + 1]; //time 누적합 -> 시청시간
    public String solution(String play_time, String adv_time, String[] logs) {
       String answer = "";
        for(int i=0; i<logs.length; i++) {
            String[] time = logs[i].split("-");
            int start_sec = conversion_sec(time[0]);
            int end_sec = conversion_sec(time[1]);
            view[start_sec] += 1;
            view[end_sec] += -1;
        }
        for(int i=1; i<view.length; i++) view[i] += view[i-1];
        cmt_sum[0] = view[0];
        for(int i=1; i<cmt_sum.length; i++) cmt_sum[i] = cmt_sum[i-1] + view[i]; //누적합 계산
        int play_time_sec = conversion_sec(play_time);
        int adv_time_sec = conversion_sec(adv_time);
        long max_time = cmt_sum[adv_time_sec-1];
        int adv_start_time = 0;
        for(int i=1; i<=play_time_sec; i++) {
            int adv_time_end = i + adv_time_sec-1;
            if(adv_time_end > play_time_sec) break;
            if(max_time < cmt_sum[adv_time_end] - cmt_sum[i-1]) {
                max_time = cmt_sum[adv_time_end] - cmt_sum[i-1];
                adv_start_time = i;
            }
        }
        answer = conversion_time(adv_start_time);
        return answer;
    }
    
    static int conversion_sec(String time) {
        String[] split_time = time.split(":");
        return Integer.parseInt(split_time[0]) * 3600 + Integer.parseInt(split_time[1]) * 60 + Integer.parseInt(split_time[2]);
    }
    static String conversion_time(int sec) {
        String str_hour = sec / 3600 < 10 ? "0" + String.valueOf(sec / 3600) : String.valueOf(sec / 3600);
        String str_min = (sec % 3600) / 60 < 10 ? "0" + String.valueOf((sec % 3600) / 60) : String.valueOf((sec % 3600) / 60);
        String str_sec = (sec % 3600) % 60 < 10 ? "0" + String.valueOf((sec % 3600) % 60) : String.valueOf((sec % 3600) % 60);
        return str_hour + ":" +  str_min + ":" + str_sec;
    }
}