광고 삽입

2025-10-16

#JAVA#프로그래머스

2분

문제 링크

문제 풀이 시간 : 1시간 12분

문제 요약

•
play_time: 동영상 총 재생시간 (HH:MM:SS)

•
adv_time: 광고 재생시간 (HH:MM:SS)

•
logs: 시청자별 재생 구간 [시작-끝] 이 최대 30만 개

•
목표: 시청자 누적 재생시간 합이 최대가 되는 광고 시작 시각을 반환 (여러 곳이면 가장 빠른 시각)

문제 풀이

잘못된 시도

처음엔 문자열 그대로 우선순위 큐를 써서 logs의 시작·끝 시각 문자열을 푸시하고 팝하면서 동시 시청자 수 변화를 추적하려 했다.

하지만 문자열 파싱·정렬 기준 처리와 동시성 집계를 함께 다루다 보니 구현이 복잡해지고, 최종적으로는 시간·가독성 면에서 비효율이라 포기했다.

그래서 생각을 바꿨다.

“모든 초를 직접 세지 말고, 변화가 있는 시점만 표시하자!”

이 문제는 누적합 과 차분 배열 개념을 이용하면 한 번의 계산으로 동시 시청자 수를 효율적으로 구할 수 있다.

핵심 아이디어

1
차분 배열 활용
각 시청 구간 [start, end) 에 대해
- •
  viewer[start] += 1
- •
  viewer[end] -= 1
  이렇게 표시한다.
이후 한 번 누적합을 돌리면,
→ 각 초의 “동시 시청자 수”를 얻을 수 있다.

1
누적합 2번 사용
첫 번째 누적합으로 “동시 시청자 수”를 만들었고,
두 번째 누적합으로 “0초부터 i초까지의 누적 시청시간 합”을 만든다.
이렇게 하면 임의의 구간 [L, R]의 합은
viewer[R] - viewer[L-1] 으로 $O(1)$ 에 계산할 수 있다.

1
슬라이딩 윈도우
광고 길이를 adv_time = A 라고 하면 시작 시각이 i일 때의 누적 시청시간은 viewer[i + A - 1] - viewer[i - 1] 이 된다.
이걸 모든 i에 대해 돌리며 최대값을 찾으면 된다.
같은 값이 여러 개면, 처음 나온 시각을 선택하면 된다.

왜 두 번 누적합을 쓰는가?

한 번 누적합만 하면 각 초의 시청자 수까지만 구할 수 있다.

하지만 광고 구간의 “합”을 빠르게 구하려면

두 번째 누적합을 이용해 prefix sum 배열을 만들어야 한다.

이렇게 하면 $O(1)$ 만에 임의의 구간 시청자 합을 구할 수 있다.

최종 코드

Java

import java.util.*;

class Solution {
    public int strToInt(String time){
        StringTokenizer st = new StringTokenizer(time, ":");
        int sec = 0;
        int t = 60*60;
        while(st.hasMoreTokens()){
            sec += Integer.parseInt(st.nextToken())*t;
            t/=60;
        }
        return sec;
    }
    
    public String intToStr(int time){ 
        int h = time/3600;
        time %= 3600;
        int m = time/60;
        time %= 60;
        return String.format("%02d:%02d:%02d",h,m,time);
    }
    
    public String solution(String play_time, String adv_time, String[] logs) {
        if(play_time.equals(adv_time))
            return intToStr(0);
        
        int ptime = strToInt(play_time);
        int atime = strToInt(adv_time);
        
        long[] viewer = new long[ptime+1];
        
        for(int i=0;i<logs.length;i++){
            StringTokenizer st = new StringTokenizer(logs[i],"-");
            int from = strToInt(st.nextToken());
            int to = strToInt(st.nextToken());
            
            viewer[from] +=1;
            viewer[to] -=1;
        }
        
        for(int i=1;i<ptime+1;i++){
            viewer[i]+=viewer[i-1];
        }
        
        for(int i=1;i<ptime+1;i++){
            viewer[i]+=viewer[i-1];
        }
        
        long max = viewer[atime];
        int start = 0;
        
        for(int i=1;i<ptime+1-atime;i++){
            long now = viewer[i+atime-1] - viewer[i-1];
            if(max<now){
                max = now;
                start = i;
            }
        }
        
        return intToStr(start);
    
    }
}