[프로그래머스] 광고 삽입(java)

코딩테스트 연습 - 광고 삽입 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 광고 삽입

어떻게 생각하고 문제를 풀었는가?

문제에서 주어진 예시처럼 광고 삽입이 가능한 구간들 중에서 시청자들의 누적 재생시간이 가장 큰 구간을 찾아야 합니다.

누적 재생시간을 구하기 위해서 구간 내 시청자들의 수를 더하는 방법을 생각하였는데, 가능한 재생 구간이 초단위로 존재할 수 있고 각 재생 구간마다 시청자들의 수를 더해야 하므로 O(N^2)의 실행시간이 예상되었습니다.

미리 각 시간마다 누적 재생시간을 계산하고, 원하는 구간의 마지막 위치에서의 누적 재생시간 - 시작 위치에서의 누적 재생시간으로 구간의 누적 재생시간을 구할 수 있습니다.

코드

import java.util.*;
class Solution {
    public String solution(String play_time, String adv_time, String[] logs) {
        int play_time_sec = convertTimetoInt(play_time);
        int adv_time_sec = convertTimetoInt(adv_time);
        long[] play_count = new long[play_time_sec+1];
        for(String log : logs){
            String[] times = log.split("-");
            play_count[convertTimetoInt(times[0])]++;
            play_count[convertTimetoInt(times[1])]--;
        }
        for(int i=1; i<=play_time_sec;i++)   play_count[i] += play_count[i-1];//i초에서 재생중인 횟수
        for(int i=1; i<=play_time_sec;i++)   play_count[i] += play_count[i-1];//i초까지 누적 재생시간
        long max = play_count[adv_time_sec-1];
        int index=0;
        for(int i=0; i+adv_time_sec<=play_time_sec; i++){
            long time = play_count[i+adv_time_sec] - play_count[i];
            if(max < time){
                index = i+1;
                max = time;
            }
        }
        return convertInttoTime(index);
    }    
    int convertTimetoInt(String str){
        String[] hms = str.split(":");
        return Integer.valueOf(hms[0])*3600 + Integer.valueOf(hms[1])*60 + Integer.valueOf(hms[2]);
    }
    String convertInttoTime(int time){
        int h = time/3600;
        time = time%3600;
        int m = time/60;
        time = time%60;
        return String.format("%02d:%02d:%02d",h,m,time);
    }
}

 

 

주어진 logs는 시청한 시작시간과 종료시간이 담겨져 있는 문자열 입니다.

시간 t에 대한 시청자의 수는 log의 시작시간마다 +1, 종료시간마다 -1을 함으로서 계산할 수 있고, 누적 재생시간은 0~t까지의 시청자 수 합으로서 구할 수 있습니다.

모든 시간에 대해 누적 재생시간을 구한 후 광고 시간동안 누적 재생시간을 계산하여 최대 값을 찾을 수 있습니다.