본문 바로가기

Algorithm/Practice

Programmers - 광고 삽입 with JAVA

 

 

 

로직

1. 전체 재생시간 및 광고 재생시간을 초로 변경한다.

2. 사람들의 로그마다 시작시간 이상 종료시간 미만으로 누적합을 구한다.

3. 0초에 광고 틀었을 때, 시청 수부터 최대한 광고를 늦게 틀었을 때 까지 최대 광고 시청수를 갱신할 때마다 정답을 갱신해준다.

(인덱스가 낮을수록 정답이기 때문에 기록할 필요 없음)

4. 정답을 시간으로 다시 표현 후 반환

 

 

틀렸던 점

1. 문제를 100퍼센트 읽지 않았다. 로그마다 실행시간은 시작시간이상 종료시간 미만임을 인지 못했다.

2. 누적 시청시간을 초단위로 구하게 되면 범위가 long으로 설정해야한다 -> 테스트 케이스 17번

3. 누적합 로직을 잘 구현하자. -> answer = i로 설정하는 실수를 하였는데 실수하지 말자.

 

 

 

 

코드

class Solution {
    public String solution(String play_time, String adv_time, String[] logs) {
        if(play_time.equals(adv_time)){
            return "00:00:00";
        }
        int play = toSecond(play_time);
        int adv = toSecond(adv_time);
        // 수정
        long[] check = new long[360000];
        for(String log : logs){
            String[] seperated_log = log.split("-");
            int start_time = toSecond(seperated_log[0]);
            int end_time = toSecond(seperated_log[1]);
            check[start_time] += 1;
            // 수정
            check[end_time] -= 1;
        }
        for(int i=1; i<360000; i++){
            check[i] += check[i-1];
        }
        // 수정
        long max_value = 0;
        int answer = 0;
        for(int i=0; i<adv; i++){
            max_value += check[i];
        }
        long now_value = max_value;
        // 수정
        for(int i=0; i+adv<play+1; i++){
            now_value += check[i+adv];
            now_value -= check[i];
            if(now_value > max_value){
                max_value = now_value;
                answer = i+1;
            }
        }
        StringBuilder sb = new StringBuilder();
        int hour = answer/3600;
        String s_hour = String.valueOf(hour);
        answer = answer % 3600;
        String s_min = String.valueOf(answer/60);
        String s_sec = String.valueOf(answer%60);
        if(s_hour.length() == 1){
            s_hour = "0"+s_hour;
        }
        if(s_min.length() == 1){
            s_min = "0"+s_min;
        }
        if(s_sec.length() == 1){
            s_sec = "0"+s_sec;
        }
        sb.append(s_hour);
        sb.append(":");
        sb.append(s_min);
        sb.append(":");
        sb.append(s_sec);
        return sb.toString();
    }
    public static int toSecond(String time){
        int hour = Integer.valueOf(time.substring(0, 2));
        int min = Integer.valueOf(time.substring(3, 5));
        int sec = Integer.valueOf(time.substring(6, 8));
        return hour*3600 + min*60 + sec;
    }
}

 

 

코드 2

- 실수 : 광고 최대시간 구할때, i<=play가 아닌 i+adv<=play로 설정했음. 즉, 종료시각이 play보다 작은지를 체크하는게 아닌 시작시간이 play보다 작은지 체크한게 실수 

class Solution {
    public String solution(String play_time, String adv_time, String[] logs) {
        if(play_time.equals(adv_time)){
            return "00:00:00";
        }
        int play = toSecond(play_time);
        int adv = toSecond(adv_time);
        long[] times = new long[360000];
        for(String log : logs){
            String[] now = log.split("-");
            int start = toSecond(now[0]);
            int end = toSecond(now[1]);
            times[start] += 1;
            times[end] -= 1;
        }
        for(int i=1; i<=play; i++){
            times[i] += times[i-1];
        }
        int result = 0;
        long max_value = 0;
        for(int i=0; i<adv; i++){
            max_value += times[i];
        }
        long mid_value = max_value;
        for(int i=adv; i<=play; i++){
            mid_value += times[i];
            mid_value -= times[i-adv];
            if(mid_value > max_value){
                result = i-adv+1;
                max_value = mid_value;
            }
        }
        return toOrigin(result);
    }
    public static int toSecond(String times){
        int result = 0;
        String[] time = times.split(":");
        result += Integer.parseInt(time[0])*3600;
        result += Integer.parseInt(time[1])*60;
        result += Integer.parseInt(time[2]);
        return result;
    }
    public static String toOrigin(int time){
        String hour = String.valueOf(time/3600);
        time %= 3600;
        String min = String.valueOf(time/60);
        String sec = String.valueOf(time%60);
        if(hour.length() == 1){
            hour = "0" + hour;
        }
        if(min.length() == 1){
            min = "0" + min;
        }
        if(sec.length() == 1){
            sec = "0" + sec;
        }
        StringBuilder sb = new StringBuilder();
        sb.append(hour);
        sb.append(":");
        sb.append(min);
        sb.append(":");
        sb.append(sec);
        return sb.toString();
    }
}