프로그래머스 광고 삽입 자바 풀이

문제 링크

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

문제 요약

play_time: 동영상 총 재생시간 (HH:MM:SS)
adv_time: 광고 재생시간 (HH:MM:SS)
logs: 시청자별 재생 구간 [시작-끝] 이 최대 30만 개
목표: 시청자 누적 재생시간 합이 최대가 되는 광고 시작 시각을 반환 (여러 곳이면 가장 빠른 시각)

문제 풀이

잘못된 시도

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

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

그래서 생각을 바꿨다.

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

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

핵심 아이디어

차분 배열 활용

누적합 2번 사용

슬라이딩 윈도우

왜 두 번 누적합을 쓰는가?

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

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

두 번째 누적합을 이용해 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);
    
    }
}

광고 삽입

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

문제 요약

문제 풀이

잘못된 시도

핵심 아이디어

왜 두 번 누적합을 쓰는가?

최종 코드

함께 읽으면 좋은 글

택배상자

롤케이크 자르기

할인 행사

숫자 변환하기