[프로그래머스,Java] Level3: 광고 삽입

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

프로그래머스

 

 

문제분석

 

시청자의 동영상 로그를 토대로,  최적의 광고타이밍을 선정해야한다.

 

동영상 상영시간은 최대 99:59:59 초,  광고의시간은 동영상시간보단 적다.

 

 

필자가 처음 접근한 전략

 

=> 이분탐색 으로 최적의 광고타이밍을 구한다

 

=> X   시청자의 동영상로그가  한쪽에 몰려있을수가 있다.   이런경우 이분탐색으로 탐지를못한다.

 

 

차선택:

=> 결국 시청자 동영상로그를 효율적으로 탐색해야한다.

=> 누적합 개념을쓴다.

 

 

누적합은   스타팅 포인트엔 +1을,    엔드포인트에서 1지점 뒤에 -1을 체크해놓는다.

 

이렇게 체크한뒤,  스타팅포인트부터 다음 인덱스로 하나씩 누적합을 진행하면, 

스타팅포인트~엔드포인트까지  1을더한것과 같은 역할을한다.

 

이행위를  30만개의 로그라고 생각해보자.

 

누적합을 안쓴다면 어땟을까?

 

로그마다  시청기록이  0~최대 동영상까지 가능하다.

30만*동영상시청 길이  만큼 +연산을할것인가?  절대 효율적이지못한다.

 

하지만 위에서 설명한대로 누적합 개념을쓰면  동영상시청길이가아닌, 단 2곳만 +1와 -1연산 한번만해주면 된다.

포인트를 먼저 찍어놓고 나중에 한번에 처리한다라고 이해하면 좋다.

 

즉, 30만*2 + 최대동영상누적합 연산이다.  이쪽이 훨씬 효율적으로 먹힌다.

 

누적합 로직이다.

여기서 조금 특수한게,  end포인트인데,  원래면 end+1지점에 -연산을 해야하지만, 

본 문제는 End포인트가 개구간(포함하지않음) 이라.. End에다 -연산을 해야한다. 

 

 

이젠 이 누적합을 써야한다.

 

우리가 알고싶은건,  최대 누적시간을 알고싶다.

 

만약, 내가   10분째에 광고를넣는다면 누적시간을 어떻게알까

 

광고시간이 20분이라고 생각한다면,

 

10분~30분사이를 알고싶다면,  우리가 구한 누적합을사용한다. 누적합 30 - 누적합 10을하면된다!

 

이렇게 말이다.

 

start_point에서 +1을 해주었는데,

 

이유는 다음과같다. 

30분에  광고시간이 20분이면,

 

10분에서 30분이 아니다.  11분에서 30분으로 봐야한다.  

=> 이것때문에 진짜 많이 헤멧다..

=> 10분에서 30분동안 광고를진행을했다해도,  30분에 들어온사람은 그 광고를 안본것마냥친다. 

 

왜냐하면 0분 10초 이런것도 다 1분이라고 간주를하나본다...

분단위로 짤라버려가지고 좀 많이 헤멨다.

 

전체풀이

 

 

class Solution {
    public String solution(String play_time, String adv_time, String[] logs) {
        String answer = "";
        
        // logs는 누적합으로 정리
        // 99:59:59는 359999 => 360000 
        
        int[] time_log = new int[360001];
        
        //누적합 진행 먼저, 스타팅과 끝나는지점+1에 포인트찍기
        for(String log:logs){
            String[] l = log.split("-");
            int start= ToInt(l[0]);
            int end = ToInt(l[1]);
            
            time_log[start]++;
            time_log[end]--;
        }
        
        int end= ToInt(play_time);
        int adv=ToInt(adv_time);
        int max_start= end-adv;
        
        //포인트를 기반으로 누적합 진행
        for(int i=1;i<time_log.length;i++){
            time_log[i]+=time_log[i-1];
        }
        
        
        long max=0;  
        long current=max;
        int start_point=0;
        
        for(int i=adv;i<=end;i++){
 
           
            current+=time_log[i]-time_log[i-adv];
            
            if(current>max){
                //광고 종료타이밍이 개구간이라 +1해야한다..
                start_point=i-adv+1;
                max=current;       
            }
            
        }   
        answer=ToTime(start_point);
      
        return answer;
    }
    
    public int ToInt(String time){
        
        String[] t = time.split(":");
        
        return Integer.parseInt(t[2])+
            Integer.parseInt(t[1])*60+
            Integer.parseInt(t[0])*60*60;
    }
    
    public String ToTime(int time){
        
        int hour= time/3600;
        String sh=String.valueOf(hour);
        if(hour<10) sh="0"+sh;
        
        
        time-=hour*3600;
        
        int min= time/60;
        time-=min*60;
        String mh=String.valueOf(min);
        
        if(min<10) mh="0"+mh;
        
        String ch=String.valueOf(time);
        if(time<10) ch="0"+ch;
        
        return sh+":"+mh+":"+ch;
        
    }
  
}