[pro] 프로그래머스 level3 72414 광고 삽입 (Java) - 투포인터

[문제]

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

프로그래머스

 

[풀이]

광고가 삽입되는 특정 구간의 시작점을 구하는 문제이기 때문에 투포인터를 생각해볼 수 있다.

100시간에 대해 초로 나타내면 360000이므로 이를 배열로 선언할 수 있고, 모든 logs의 구간에 대해서 카운트를 증가시킴으로써 각 초마다 몇 명이 듣는지를 나타낸다.

이제 고정된 광고의 길이가 주어지므로 포인터를 이동시켜가며 가장 큰 구간합이 되는 시작점을 반환해주면 된다.

이때 완전탐색을 하면 전체 M 길이 동영상에 광고 N 이라고 했을 때 O(M*N)이 되므로 시간초과가 발생할 수 있다. 하지만 광고의 길이가 고정되어있기 때문에 O~K까지의 구간합 다음인 1~K+1 까지는 다시 탐색할 필요 없이, 맨 앞 index의 수를 빼주고, 다음 index의 수를 더해줌으로써 O(M)만으로 해결 가능하다. 이를 위해 Queue를 사용할 수 있다.

 

[코드]

 

import java.util.*;

class Solution {
    int[] cnt = new int[360000]; //100시간 -> 360000초
    public String solution(String play_time, String adv_time, String[] logs) {
        String answer = "";
        //공익광고가 들어갈 시작 시각을 구해서 return
        
        for(String l:logs){
            int start = toSeconds(l.substring(0, 8));
            int end = toSeconds(l.substring(9, l.length()));
            
            for(int i=start; i<end; i++){
                cnt[i]++;
            }
        }
        
        int play = toSeconds(play_time);
        int adv = toSeconds(adv_time);
        
        Queue<Integer> q = new LinkedList<>();
        
        long sum = 0;
        for(int i=0; i<adv; i++){
            sum += cnt[i];
            q.add(cnt[i]);
        }
        
        //구간합 구하기
        long maxSum = sum;
        int start = 0;
        for(int i=adv; i<play; i++){
            sum -= q.poll();
            sum += cnt[i];
            q.add(cnt[i]);
            
            if(sum > maxSum){
                maxSum = sum;
                start = i-adv+1;   
            }
        }
        
        answer = toString(start);
        
        return answer;
    }
    
    public String toString(int seconds){
        String s = "";
        int sec = seconds%60;
        seconds /= 60;
        int m = seconds%60;
        int h = seconds/60;

        if(h < 10){
            s += "0";
        }
        s += Integer.toString(h);
        s += ":";
        
        if(m<10){
            s += "0";
        }
        s += Integer.toString(m);
        s += ":";
        
        if(sec<10){
            s += "0";
        }
        s += Integer.toString(sec);
        
        return s;
       
    }
    
    public int toSeconds(String str){
        String hour = str.substring(0, 2);
        String minute = str.substring(3, 5);
        String sec = str.substring(6, str.length());
        
        int h = Integer.parseInt(hour) * 60 * 60;
        int m = Integer.parseInt(minute) * 60;
        int s = Integer.parseInt(sec);
        
        return h+m+s;
    }
}