[카카오 기출 문제]광고 삽입- 레벨 3, 아이디어 + 윈도우 슬라이딩

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

프로그래머스

 

문제를 푸는 논리입니다.

전체 동영상 재생시간이 "02:03:55" 로 주어졌다고 가정합니다.

2시간 - > 2 * 60 * 60 초 = 7200

3분-> 3 * 60 초 = 180

55초 = 55

= 7435

timerecord[7435 + 1]의 배열을 만들어줍니다.

그리고 사람들이 동영상을 플레이한 기록인 log를 위와 같이 시분초 형식을 초 형식으로 변환하여 +1 해주면 됩니다.

그 이후 동영상 플레이 길이만큼의 합을 먼저 구해준뒤, 하나씩 갱신하면서 나아가면됩니다.

 

 

기억해야할점들

첫번째, String.format 함수로 쉽게 HH:MM:SS 형식을 나타낼 수 있습니다.

https://blog.jiniworld.me/68 를 참고했습니다.

String.format("%02d:%02d:%02d", maxidx/(60*60), (maxidx%(60*60))/60, (maxidx%(60*60))%60);

 

두번쨰, maxidx, timereocrds[]의 배열인덱스는 시간의 각초를 의미합니다.

timerecords[181]은 3분 1초를 의미합니다. 그러므로 마지막에 시간을 나타낼때 maxidx 값을 연산하여 시간을 리턴해줍니다.

 

세번째, 초를 hour, minutes, second 로 나타내는연산입니다.

초가 3680 이라고 가정합니다.

3680 / (60 *60 ) = 1시간

(3680 % (60 * 60)) / 60 =  (80) / 60 = 1분

(3680 % (60 * 60)) % 60 = 20초

 

 

 

코드입니다.

class Solution {
    //100시간을 초로변환한 동영상 배열을 선언
    public String solution(String play_time, String adv_time, String[] logs) {
        String answer = "";
        
        int play_time_int = timeConvertToSecondInt(play_time);
        int adv_time_int = timeConvertToSecondInt(adv_time);
        
        System.out.println(play_time_int);
        System.out.println(adv_time_int);
        int[] timerecord = new int[play_time_int + 1];
        
        for(String log : logs){
            int startlog = timeConvertToSecondInt(log.substring(0,8));
            int endlog = timeConvertToSecondInt(log.substring(9,17));
            
            for(int i=startlog;i<endlog;i++){
                timerecord[i] += 1;
            }
        }
        
        int maxidx = 0;
        long maxtime = 0;
        for(int i=0;i<adv_time_int;i++){
            maxtime += timerecord[i];
        }
        
        System.out.println(maxtime);
        long currtime = maxtime;
        for(int i=adv_time_int; i<play_time_int;i++){
            currtime += timerecord[i];
            currtime -= timerecord[i - adv_time_int];
            
            if(maxtime < currtime){
                maxidx = i - adv_time_int + 1;
                maxtime = currtime;
            }
        }
            
        return String.format("%02d:%02d:%02d", maxidx/(60*60), (maxidx%(60*60))/60, (maxidx%(60*60))%60);
    }
    
    public int timeConvertToSecondInt(String timeformat){
        String[] temp = timeformat.split(":");
        int hour = Integer.parseInt(temp[0]) * 60 * 60;
        int minute = Integer.parseInt(temp[1]) * 60;
        int second = Integer.parseInt(temp[2]);
        
        return hour + minute + second;
    }
}

 

네번째, long maxsum을 사용해야합니다. 

long maxsum, sum =0 를 사용하여야 제출시 완전한 정답이 됩니다.

- logs는 크기가 1 이상 300,000 이하인 문자열 배열입니다.

그리고 300,000 개의 query, 그리고 시간은 100시간 (100 * 3600)이므로

100 * 3600 * 300,000 = 108,000,000,000 //108억이므로 int는 21억까지 가능하므로 long을 사용하여야 overflow가 나지 않습니다.

 

다섯번째, 

1. 동영상 재생시간 = 재생이 종료된 시각 - 재생이 시작된 시각(예를 들어, 00시 00분 01초부터 00시 00분 10초까지 동영상이 재생되었다면, 동영상 재생시간은 9초 입니다.) ↩

이 의미는 01초 부터 10초까지 간다고하면, 1, 2, 3, 4, 5, 6, 7, 8, 9 까지 라는 뜻입니다.

우선 adv_sum 즉, 만약 adv_sum이 10이라고한다면 0초부터 9초까지의 record합을 구합니다.

그 이후 adv_sum=10 부터 새롭게 시작하며 슬라이딩 윈도우를 시작하는데

이떄 최대값보다 크다면 갱신되면서 maxstartindex = 15 - 15 + 1; 을 해줘야 maxstartindex = 1이 됩니다.

마지막값은 초로 포함되지 않기에         

maxstartindex = i - adv_sum + 1;  

이 계산식이 나옵니다.

for(int i=0;i<adv_sum;i++){
    sum += record[i];
    // System.out.println(" "+record[i]);
}
maxsum = sum;
maxstartindex = 0;
for(int i=adv_sum;i<playtime; i++){
    sum += record[i];
    sum -= record[i - adv_sum];
    if(maxsum < sum){
        maxsum = sum;
        maxstartindex = i - adv_sum + 1;
    }    
}

 

 

 

두번쨰 풀어본 코드입니다.

import java.util.*;
import java.util.Map.*;
import java.io.*;
class Solution {
    int[] record;
    String answer = "";
    public String solution(String play_time, String adv_time, String[] logs) {
        
        String[] play_time_temp = play_time.split(":");
        int h = Integer.parseInt(play_time_temp[0]);
        int m = Integer.parseInt(play_time_temp[1]);
        int s = Integer.parseInt(play_time_temp[2]);
        
        int playtime = h * 60 * 60 + m * 60 + s;
        int[] record = new int[playtime + 1];
        
        for(int i=0;i<logs.length;i++){
            String[] temp = logs[i].split("-");
            int start_h = Integer.parseInt(temp[0].substring(0,2));
            int start_m = Integer.parseInt(temp[0].substring(3,5));
            int start_s = Integer.parseInt(temp[0].substring(6,8));
            
            int end_h = Integer.parseInt(temp[1].substring(0,2));
            int end_m = Integer.parseInt(temp[1].substring(3,5));
            int end_s = Integer.parseInt(temp[1].substring(6,8));
            
            int start = start_h * 60 * 60 + start_m * 60 + start_s;
            int end = end_h * 60 * 60 + end_m * 60 + end_s;
            
            // System.out.println("start "+ start + "end "+ end);
            for(int j=start; j<end; j++){
                record[j] += 1;
            }
        }
        
        String[] adv_temp = adv_time.split(":");
        int adv_h = Integer.parseInt(adv_temp[0]) * 60 * 60;
        int adv_m = Integer.parseInt(adv_temp[1]) * 60;
        int adv_s = Integer.parseInt(adv_temp[2]);
        int adv_sum = adv_h + adv_m + adv_s;
        
        long sum = 0;
        long maxsum = 0;
        int maxstartindex = 0;     
        
        for(int i=0;i<adv_sum;i++){
            sum += record[i];
            // System.out.println(" "+record[i]);
        }
        maxsum = sum;
        maxstartindex = 0;
        for(int i=adv_sum;i<playtime; i++){
            sum += record[i];
            sum -= record[i - adv_sum];
            if(maxsum < sum){
                maxsum = sum;
                maxstartindex = i - adv_sum + 1;
            }    
        }

        // maxstartindex += 1;
        String answer = String.format("%02d:%02d:%02d", maxstartindex / 3600, (maxstartindex%3600)/60, (maxstartindex%(3600)%60) );
        System.out.println(answer);
        return answer;
    }
}