[카카오 2021 공채] 광고 삽입

2021년 카카오 공채 광고 삽입 해설입니다

---

광고의 누적 시청 시간이 MAX가 되는 시작 시간을 구하는 문제입니다. 누적된 시청 시간까지 구할 필요 없이 누적 시청 인원만 구하면 됩니다.

문제를 단순화 하면 전체 구간에서 특정 길이 만큼의 구간 합이 가장 큰 구간을 구하는 것입니다. 전체 구간을 배열로 만들기 위해 주어진 "HH:MM:SS" 문자열을 모두 초(Second)로 변환합니다.

그리고 logs에 기록된 시청 시간을 초로 변환하여 배열에 기록합니다. 배열에 시청 인원을 기록하는 방법은 두 가지가 있습니다.

1. 시작과 끝 마킹 후 합하기
   
   시청 시작 시간에 1을 더하고, 끝 시간에 -1을 더하는 방법입니다. 마킹이 끝난 후 현재 원소에서 이전 원소의 값을 더하면 전체 구간에서 누적 시청자 수를 구할 수 있습니다.

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

2. 바로 합하기
   
   시작 ~ 끝 시간을 반복문을 통해 바로 배열에 기록하는 방법입니다.

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

2번 방법의 경우도 올바른 방법이긴 하지만 불필요하게 구간을 반복해서 조회하기 때문에 1번 방법에 비해 시간이 좀 더 오래 걸릴 것으로 예샹됩니다.

누적 시청자 기록이 끝이 나면, 최대 누적 시청자를 가지는 특정 구간을 구해야합니다. 큐를 사용하는 방법도 있겠지만 단순히 배열의 인덱스를 사용하여 해결할 수 있습니다.

먼저 0 ~ advTime - 1 까지의 구간 합을 구하고, 구간을 이동하면서 새로운 시청자 수는 더하고 구간을 벗어난 시청자 수는 뺍니다.

long currentCount = 0;
for(int i=0;i<advTime;i++) {
    currentCount += playCount[i];
}

long maxCount = currentCount;
int maxIdx = 0;
for (int i=advTime;i <= playCount;i++) {
    currentCount = currentCount + playCount[i] - playCount[i - advTime];

    if (maxCount < currentCount) {
        maxCount = currentCount;
        maxIdx = i - advTime + 1;
    }
}

Java

class Solution {
    public String solution(String play_time, String adv_time, String[] logs) {
        int playTime = parseSecond(play_time);
        int advTime = parseSecond(adv_time);
        long[] playCount = new long[playTime + 1];

        for (String log : logs) {
            int start = parseSecond(log.split("-")[0]);
            int end = parseSecond(log.split("-")[1]);

            playCount[start]++;
            playCount[end]--;
        }

        for (int i = 1;i <= playTime;i++) {
            playCount[i] += playCount[i - 1];
        }

        long currentCount = 0;
        for (int i = 1;i < advTime;i++) {
            currentCount += playCount[i];
        }

        long maxCount = currentCount;
        int maxIdx = 0;

        for (int i = advTime;i <= playTime;i++) {
            currentCount = currentCount + playCount[i] - playCount[i - advTime];

            if (maxCount < currentCount) {
                maxCount = currentCount;
                maxIdx = i - advTime + 1;
            }
        }

        String answer = String.format("%02d:%02d:%02d", maxIdx / 3600, (maxIdx / 60) % 60, maxIdx % 60);
        return answer;
    }

    private int parseSecond(String time) {
        String[] hms = time.split(":");
        return Integer.parseInt(hms[0]) * 3600 + Integer.parseInt(hms[1]) * 60 + Integer.parseInt(hms[2]);         
    }
}

Python

def solution(play_time, adv_time, logs):
    play_time = parse_second(play_time)
    adv_time = parse_second(adv_time)
    play_count = [0 for _ in range(play_time + 1)]

    for log in logs:
        start, end = map(parse_second, log.split("-"))
        play_count[start] += 1
        play_count[end] -= 1

    for i in range(1, play_time):
        play_count[i] += play_count[i - 1]

    current_count = sum(play_count[1:adv_time])
    max_count, max_idx = current_count, 0

    for i in range(adv_time, play_time + 1):
        current_count = current_count + play_count[i] - play_count[i - adv_time]

        if (max_count < current_count):
            max_count = current_count
            max_idx = i - adv_time + 1

    return "%02d:%02d:%02d" % (max_idx / 3600, max_idx / 60 % 60, max_idx % 60)

def parse_second(time):
    h, m, s = map(int, time.split(":"))
    return h * 3600 + m * 60 + s