Lv 3. 광고 삽입

 

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

 

 

📌 자바(Java)로 푸는 광고 삽입 문제 - 프로그래머스 📺📊

---

🔎 문제 개요

 

프로그래머스 Lv.3 - 광고 삽입 문제입니다.

하루 동안의 동영상 재생 기록(logs)이 주어졌을 때,

광고를 삽입할 시작 시간을 정해서, 전체 광고 누적 시청 시간을 최대화하는 문제입니다.

---

💡 예제 입력

play_time = "02:03:55"
adv_time = "00:14:15"
logs = [
  "01:20:15-01:45:14",
  "00:40:31-01:00:00",
  ...
]

💡 예제 출력

"01:30:59"

➡ 해당 시각에 광고를 삽입했을 때 광고 누적 시청 시간이 최대가 되는 시각을 반환

---

🛠 알고리즘 접근 방식

 

이 문제는 누적합(Prefix Sum) + 슬라이딩 윈도우 기법을 활용하여 해결합니다.

 

✏️ 핵심 전략

• 시간 단위를 초 단위로 변환하여 배열 인덱스로 활용

• viewers[i]: i초에 시청 중인 사람 수

• 로그를 통해 시청자 수 변화를 기록 (시작 시 +1, 종료 시 -1)

• 두 번 누적합:

1. 누적 시청자 수

2. 누적 시청 시간

• 슬라이딩 윈도우로 광고 길이만큼 구간을 순회하며 최대 시청 시간 구간 찾기

 

---

🔹 Java 코드 해설

import java.util.*;

class Solution {
    public String solution(String play_time, String adv_time, String[] logs) {
        int playLength = toSeconds(play_time);
        int advLength = toSeconds(adv_time);

        long[] viewers = new long[playLength + 2];  // 1초 단위 누적

        for (String log : logs) {
            int start = toSeconds(log.substring(0, 8));
            int end = toSeconds(log.substring(9, 17));
            viewers[start] += 1;
            viewers[end] -= 1;
        }

        // 1차 누적합: 초당 시청자 수
        for (int i = 1; i <= playLength; i++) {
            viewers[i] += viewers[i - 1];
        }

        // 2차 누적합: 시청자 수의 누적합 = 누적 시청 시간
        for (int i = 1; i <= playLength; i++) {
            viewers[i] += viewers[i - 1];
        }

        long maxViewTime = viewers[advLength - 1];
        int answerTime = 0;

        for (int i = advLength; i <= playLength; i++) {
            long viewTime = viewers[i] - viewers[i - advLength];
            if (viewTime > maxViewTime) {
                maxViewTime = viewTime;
                answerTime = i - advLength + 1;
            }
        }

        return toTime(answerTime);
    }

    private int toSeconds(String time) {
        int h = Integer.parseInt(time.substring(0, 2));
        int m = Integer.parseInt(time.substring(3, 5));
        int s = Integer.parseInt(time.substring(6, 8));
        return h * 3600 + m * 60 + s;
    }

    private String toTime(int seconds) {
        int h = seconds / 3600;
        int m = (seconds % 3600) / 60;
        int s = seconds % 60;
        return String.format("%02d:%02d:%02d", h, m, s);
    }
}

 

---

🔍 코드 설명

 

📌 1. 로그 기반 시청자 수 변화 기록

viewers[start] += 1;
viewers[end] -= 1;

✔ 각 로그의 시작 시점에는 시청자 수 +1, 종료 시점에는 -1

✔ 이후 누적합을 통해 초당 시청자 수 계산

 

---

📌 2. 누적합 2번 활용

// 첫 번째 누적합: 초당 시청자 수
for (int i = 1; i <= playLength; i++) {
    viewers[i] += viewers[i - 1];
}
// 두 번째 누적합: 누적 시청 시간
for (int i = 1; i <= playLength; i++) {
    viewers[i] += viewers[i - 1];
}

✔ 첫 번째 누적합은 초마다 시청자 수 계산

✔ 두 번째 누적합은 누적 시청 시간 계산을 위한 준비

 

---

📌 3. 슬라이딩 윈도우로 최적 구간 탐색

long viewTime = viewers[i] - viewers[i - advLength];

✔ i초까지 누적 시청 시간 - (i - 광고시간)초까지 누적 시청 시간

✔ 가장 누적 시청 시간이 큰 구간의 시작 시각을 저장

 

---

🏆 정리

 

✅ 핵심 포인트

 

✔ 초 단위 배열 + 누적합으로 시간 효율성 확보

✔ 광고 시청 시간 최대 구간을 슬라이딩 윈도우로 빠르게 탐색

✔ 문자열 ↔ 초 변환 유틸리티 함수 사용 (toSeconds, toTime)

---

🎯 이 알고리즘의 장점

 

✅ 1초 단위로 변환해 정밀한 시청 시간 계산 가능

✅ 누적합과 구간 합을 이용해 광고 삽입 시점을 효율적으로 찾음

✅ 많은 로그 데이터가 있어도 빠르게 처리 가능

 

---

이 글이 도움이 되셨다면 좋아요와 공유 부탁드립니다! 😊