(코테) 프로그래머스_광고 삽입 * 윈도우 슬라이딩

 

문제 링크

 

 

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

 

 

 

class Solution {
    public String solution(String play_time, String adv_time, String[] logs) {                        
        int play=intChange(play_time);
        int adv=intChange(adv_time);
                
        if (adv <= 0 || adv > play) return "00:00:00";
        
        long[] arrCheck = new long[play+2];
        //구간 지정 배열로 
        for(String next:logs){
            String[] arr=next.split("-");
            int start = intChange(arr[0]);
            int end = intChange(arr[1]);
            
            //if(start<0 || end>play) return "00:00:00";
                       // [start, end) 반열림, 범위 클램프
            if (start < 0) start = 0;
            if (end > play) end = play;
            if (start >= end) continue; // 무효/0길이 구간 스킵
            
            
            arrCheck[start] += 1;
            arrCheck[end] -= 1;                                    
        }        
        
        //배열별 누적 더하기
        long[] arrSum = new long[play+1];
        arrSum[0] = arrCheck[0];
        for(int i=1;i<=play;i++){
          arrSum[i] = arrCheck[i]+arrSum[i-1];
        } 
        
        long best = 0;
        int bestStart =0;
        
        //초기 광고 값
        for(int i=0;i<adv;i++) best+=arrSum[i];
        long diff = best;
        //광고 길이만큼 윈도우 슬라이스로 배열별 가장 큰 값 시작점 구하기        
        for(int i= 1; i+adv-1<play;i++){                        
            
            diff-=arrSum[i-1];
            diff+=arrSum[i+adv-1];
            
            if(diff>best){
                bestStart = i;
                best=diff;
            }            
        }        
        
        
        return stringChange(bestStart);
    }
    
    public int intChange(String time){
        String[] strr = time.split(":");
        int hour = Integer.parseInt(strr[0]) * 60 * 60;
        int minitue = Integer.parseInt(strr[1]) * 60;
        int sceond = Integer.parseInt(strr[2]);
        
        return hour+minitue+sceond;
    }
    
    public String stringChange(int time){        
                        // 60 *60 3000    60*50
                        //1시간 30분   14초   3600 + 1800 + 14   ->  5414/  
        int h = time / (60*60); 
        int m = time % (60*60)/60;
        int s = time % (60*60) % 60;                
        
        return String.format("%02d:%02d:%02d",h,m,s);
    }
}

 

회고

코테 푼것중 문제도 어렵고 풀이도 되게 생소하고 어려웠다... (예외처리도 많음..)

꼬여있는게 많다고 생각한다. 인덱스 관리도 그렇고.

 

1.각 사용자의 시작 종료 시간을 전체 총 길이에서  각 배열별 (시분초를 초로 나눈 배열의 총 값) 을 나열하여 시작 값에 1 종료 값에 -1 넣어      배열의 값에 누적값?을 적용하여   가장 큰 값 구함. (그 구간이 사용자 가장 많은 구간)

 

2.  그리고 그 누적된 배열에  adv (광고길이 만큼 *윈도우슬라이딩 핵심)를 옆으로 넘기며 가장 큰 값의 구간의 시작 값을 구함.

 

 

예시) 

광고 시간 3

 

인덱스            - 0 1 2 3 4 5 6 7 8 9 10 11 12 13  14 15

배열예시          - ㅁㅁㅁㅁㅁㅁㅁㅁㅁ ㅁ ㅁ ㅁ  ㅁ  ㅁ   ㅁ  

시작 종료 표시 -  0  1 0 1 0 -1 0 0-1 0 0 1 0 0 -1  1   -1   (예시임  1은 시작  -1 종료) 

 누적 배열        - 0   1 1 2 2 1  1 1 0 0 0 1 0 0 -1  0   -1  

 

 

* 위 상황에서 눈으로 봤을때 누적 배열 인덱스 4~5 구간 2인 값 구간이 가장 커보임 (사용자도 가장 많다는 뜻)

 

광고 시간은 3으로 고정이니  3의 길이를 0 배열부터 옆으로 넘겨가며 누적배열의 3개의 구간값이 가장 큰 구간의 시작값을 구하면 된다.  (그게 가장 많이 본 사용자 구간)