프로그래머스 광고삽입 [JAVA]

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

프로그래머스

 

 

해당 문제는 누적합의 개념을 알아야 시간안에 풀 수 있다.

시간은 초로 환산하여 계산하면 간단히 구현할 수 있다.

 

 

주의 1. 재생시간에서 끝나는 시간 end 에서는 -1 을 해주어야 한다.

 

• 시청 구간의 의미: 예를 들어, 로그에 00:00:00 - 00:00:10이라고 되어 있으면, 일반적으로 시청이 00:00:00에서 시작하고, 00:00:10이 시작되는 순간에 끝난다는 것을 의미합니다. 즉, 실제로 시청은 00:00:00부터 00:00:09까지 이루어지며, 00:00:10에는 시청이 끝났다고 볼 수 있습니다.

 

 

• 시청 기록: 00:00:00 - 00:00:10
• getSeconds(s[0]) = 0 (시작 시각)
• getSeconds(s[1]) = 10 (끝나는 시각)
• 실제로 시청한 시간 범위는 0초부터 9초까지입니다.

주의 2.  sum 값 long 형으로 선언

시간을 초로 환산하면 최대 99:59:59

이므로 100 * 60 * 60 = 360,000 이 된다.

이때 logs 은 최대 300,000 

값을 가질 수 있으므로 sum 이 가질 수 있는 최대 수는 300,000*360,000 이 되므로 long 형으로 선언하여야 한다.

 

누적합 개념 사용 전 코드(시간 초과)

 

 

import java.util.*;
class Solution {
    public String solution(String play_time, String adv_time, String[] logs) {
        
        int pt = getSeconds(play_time);
        int at = getSeconds(adv_time);
        int[] time = new int[360_000];
        for(String log : logs){
            String[] s = log.split("-");
            int start = getSeconds(s[0]);
            int end = getSeconds(s[1])-1; // 끝 시간이 포함되지 않도록 조정
            for(int i=start; i<=end; i++){
                time[i]++;
            }
        }
        int sum =0;
        int ans = 0;
        for(int i=1; i <= at; i++){
            sum += time[i];
        }

        long max = sum;
        for(int i=1; i<=pt- at; i++){ 
            sum -= time[i-1];
            sum += time[i + at-1];
            if(max < sum){
                ans = i;
                max = sum;
            }
        }
    
        String answer = getTime(ans);
        
        return answer;
    }
    
    public int getSeconds(String play_time){
        String[] s = play_time.split(":");
        int hour = Integer.parseInt(s[0])*3600;
        int min = Integer.parseInt(s[1])*60;
        int sec = Integer.parseInt(s[2]);
        return hour + min + sec;
    }
    
     public String getTime(int sec){
        StringBuilder sb = new StringBuilder();
        int hour = sec/3600;
        sec = sec % 3600;
        int min = sec/60;
        sec = sec % 60;
        if(0<= hour && hour < 10) sb.append("0");
        sb.append(hour).append(":");
        if(0<= min && min < 10) sb.append("0");
        sb.append(min).append(":");
        if(0<= sec && sec < 10) sb.append("0");
        sb.append(sec);
        return sb.toString();
    }
}

누적합 개념 사용 전 코드(시간 초과)

 

 

누적합풀이

import java.util.*;
class Solution {
    public String solution(String play_time, String adv_time, String[] logs) {
        
        int pt = getSeconds(play_time);
        int at = getSeconds(adv_time);
        int[] time = new int[360_000];
        for(String log : logs){
            String[] s = log.split("-");
            int start = getSeconds(s[0]);
            int end = getSeconds(s[1]);
            time[start]++;
            time[end]--;
        }
        long sum =0;
        int ans = 0;
         for(int i=1; i < 360_000; i++){
            time[i] += time[i-1];
        }
        for(int i=1; i < at; i++){
            sum += time[i];
        }

        long max = sum;
        int startTime=1;
        while(startTime +at <= pt){
            sum -= time[startTime-1];
            sum += time[startTime + at-1];
            if(max < sum){
                ans = startTime;
                max = sum;
            }
            startTime++;
        }
      
    
        String answer = getTime(ans);
        
        return answer;
    }
    
    public int getSeconds(String play_time){
        String[] s = play_time.split(":");
        int hour = Integer.parseInt(s[0])*3600;
        int min = Integer.parseInt(s[1])*60;
        int sec = Integer.parseInt(s[2]);
        return hour + min + sec;
    }
    
     public String getTime(int sec){
        int hour = sec/3600;
        sec = sec % 3600;
        int min = sec/60;
        sec = sec % 60;
        return String.format("%02d:%02d:%02d", hour, min, sec);
    }
}