[Programmers] 광고 삽입 (Python, Java)

• 누적합을 모른다면 사실상 시간 안에 풀 수 없는 문제

Solution

Python

from typing import List


def to_second(time: str) -> int:
    second = 0

    time_split = time.split(':')
    h, m, s = time_split[0], time_split[1], time_split[2]

    if h < '10':
        second += int(h[1]) * 60 * 60
    else:
        second += int(h) * 60 * 60

    if m < '10':
        second += int(m[1]) * 60
    else:
        second += int(m) * 60

    if s < '10':
        second += int(s[1])
    else:
        second += int(s)

    return second


def to_time(second: int) -> str:
    h = second // 3600
    m = (second % 3600) // 60
    s = second % 60

    return to_time_str(h) + ':' + to_time_str(m) + ':' + to_time_str(s)


def to_time_str(num: int) -> str:
    if num < 10:
        return '0' + str(num)

    return str(num)


def solution(play_time: str, adv_time: str, logs: List[str]) -> str:
    answer = 0

    play_time_second = to_second(play_time)
    adv_time_second = to_second(adv_time)

    # 초당 시청자 수 (누적합 배열)
    total_viewer_for_second = [0 for _ in range(play_time_second + 1)]

    # 각 구간의 시청자 수 체크
    # total_viewer_for_second[time] = (time 시각에 시작한 시청자 수) - (time 시각에 종료한 시청자 수)
    for log in logs:
        start, end = log.split('-')
        start_sec = to_second(start)
        end_sec = to_second(end)

        total_viewer_for_second[start_sec] += 1
        total_viewer_for_second[end_sec] -= 1

    # 누적합 계산 1회 (1초 간격으로 누적합 계산)
    # total_viewer_for_second[time] = (time 시각부터 time + 1 시각까지의 1초간의 구간을 포함한 시청자 수)
    for i in range(1, len(total_viewer_for_second)):
        total_viewer_for_second[i] += total_viewer_for_second[i - 1]

    # 누적합 계산 2회 (해당 초까지의 누적 시청자 계산)
    # total_viewer_for_second[time] = (0초부터 time + 1 시각까지의 구간을 포함한 누적 시청자 수)
    for i in range(1, len(total_viewer_for_second)):
        total_viewer_for_second[i] += total_viewer_for_second[i - 1]

    max_viewer_from_zero_time = total_viewer_for_second[adv_time_second - 1]
    for i in range(0, len(total_viewer_for_second) - adv_time_second):
        target = total_viewer_for_second[i + adv_time_second] - total_viewer_for_second[i]
        if target > max_viewer_from_zero_time:
            max_viewer_from_zero_time = target
            answer = i + 1

    print(answer)
    return to_time(answer)


print(solution("02:03:55", "00:14:15",
               ["01:20:15-01:45:14", "00:40:31-01:00:00", "00:25:50-00:48:29", "01:30:59-01:53:29",
                "01:37:44-02:02:30"]))

• Java로 풀려면 long으로 변환해야 함
  • 안 그러면 17번에서 계속 에러 남

Java

package programmers.sully.week39;

public class InsertAd {

    public static long toSecond(String time) {
        long second = 0;

        String[] timeSplit = time.split(":");
        int h = Integer.parseInt(timeSplit[0]);
        int m = Integer.parseInt(timeSplit[1]);
        int s = Integer.parseInt(timeSplit[2]);

        second += h < 10 ? Integer.parseInt(timeSplit[0].substring(1)) * 60 * 60 : h * 60 * 60;
        second += m < 10 ? Integer.parseInt(timeSplit[1].substring(1)) * 60 : m * 60;
        second += s < 10 ? Integer.parseInt(timeSplit[2].substring(1)) : s;

        return second;
    }

    public static String toTime(long second) {
        long h = second / 3600;
        long m = (second % 3600) / 60;
        long s = second % 60;

        return toTimeStr(h) + ":" + toTimeStr(m) + ":" + toTimeStr(s);
    }

    public static String toTimeStr(long num) {
        return num < 10 ? "0" + num : String.valueOf(num);
    }

    public static String solution(String playTime, String advTime, String[] logs) {
        long answer = 0;

        long playTimeSecond = toSecond(playTime);
        long advTimeSecond = toSecond(advTime);

        // 초당 시청자 수 (누적합 배열)
        long[] totalViewerForSecond = new long[(int) (playTimeSecond + 1)];

        // 각 구간의 시청자 수 체크
        // totalViewerForSecond[time] = (time 시각에 시작한 시청자 수) - (time 시각에 종료한 시청자 수)
        for (String log : logs) {
            String[] logSplit = log.split("-");
            long startSec = toSecond(logSplit[0]);
            long endSec = toSecond(logSplit[1]);

            totalViewerForSecond[(int) startSec]++;
            totalViewerForSecond[(int) endSec]--;
        }

        // 누적합 계산 1회 (1초 간격으로 누적합 계산)
        // totalViewerForSecond[time] = (time 시각부터 time + 1 시각까지의 1초간의 구간을 포함한 시청자 수)
        for (int i = 1; i < totalViewerForSecond.length; i++) {
            totalViewerForSecond[i] += totalViewerForSecond[i - 1];
        }

        // 누적합 계산 2회 (해당 초까지의 누적 시청자 계산)
        // totalViewerForSecond[time] = (0초부터 time + 1 시각까지의 구간을 포함한 누적 시청자 수)
        for (int i = 1; i < totalViewerForSecond.length; i++) {
            totalViewerForSecond[i] += totalViewerForSecond[i - 1];
        }

        long maxViewerFromZeroTime = totalViewerForSecond[(int) (advTimeSecond - 1)];
        for (int i = 0; i < totalViewerForSecond.length - advTimeSecond; i++) {
            long target = totalViewerForSecond[i + (int) advTimeSecond] - totalViewerForSecond[i];
            if (target > maxViewerFromZeroTime) {
                maxViewerFromZeroTime = target;
                answer = i + 1;
            }
        }

        System.out.println(answer);
        return toTime(answer);
    }

}

Reference

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