2021 KAKAO BLIND RECRUITMENT(광고 삽입)

문제 유형

• 누적합

문제 접근

• 답
  • 제일 많은 시청자가 보기 위한 광고 시작 타임
• 주어지는 정보
  • 영상 최대 길이 99:59:59
  • 시청자 수 최대 300,000
• 후보
  • 완전탐색
    • 가능
      • 누적합을 써서 각 시간별 시청자 수를 배열로 기록
      • 해당 배열을 전부 훑으면서 시청자 수가 제일 많을 때를 찾아냄
• 설명
  • 누적합
    • int[] temp : 시청자의 시청 시작, 종료 시간을 표기
    • int[] logsTime : 각 시간별 시청자의 총합을 표기

public void setLogsTime(String[] logs){
    logsTime = new int[MAX];
    int[] temp = new int[MAX];
    
    for(int i = 0; i<logs.length; i++){
        logs[i] = logs[i].replace('-', ':');
        String[] log = logs[i].split(":");
        
        int start = 0;
        for(int j = 0; j<3; j++){
            start += Integer.parseInt(log[j]) * timeUnit[j];
        }
        
        int end = 0;
        for(int j = 3; j<6; j++){
            end += Integer.parseInt(log[j]) * timeUnit[j-3];
        }
        
        temp[start]++;
        temp[end]--;
    }
    
    int sum = 0;
    for(int i = 0; i<MAX; i++){
        sum += temp[i];
        logsTime[i] = sum;
    }
}

 

 

제일 시청자가 많이 보는 시작 시간 구하기

public int getTimeLine(String adv_time){
      long answer = 0;
      int timeLine = 0;
      
      
      int advLength = 0;
      String[] temp = adv_time.split(":");
      for(int i = 0; i<3; i++){
          advLength += Integer.parseInt(temp[i]) * timeUnit[i];
      }
      
      long sum = 0;
      for(int i = 0; i<advLength; i++){
          sum += logsTime[i];
      }
      
      answer = sum;        
      for(int i = 1; i < MAX - advLength; i++){
          sum += logsTime[i + advLength - 1] - logsTime[i-1];
          
          if(answer < sum){
              answer = sum;
              timeLine = i;
          }
      }
      
      return timeLine;

  }

 

 

 

전체 코드

class Solution {
    int MAX = 0;
    int[] logsTime;
    int[] timeUnit = {60*60, 60, 1};
    
    public int getTimeLine(String adv_time){
        long answer = 0;
        int timeLine = 0;
        
        
        int advLength = 0;
        String[] temp = adv_time.split(":");
        for(int i = 0; i<3; i++){
            advLength += Integer.parseInt(temp[i]) * timeUnit[i];
        }
        
        long sum = 0;
        for(int i = 0; i<advLength; i++){
            sum += logsTime[i];
        }
        
        answer = sum;        
        for(int i = 1; i < MAX - advLength; i++){
            sum += logsTime[i + advLength - 1] - logsTime[i-1];
            
            if(answer < sum){
                answer = sum;
                timeLine = i;
            }
        }
        
        return timeLine;

    }
    
    public void setLogsTime(String[] logs){
        logsTime = new int[MAX];
        int[] temp = new int[MAX];
        
        for(int i = 0; i<logs.length; i++){
            logs[i] = logs[i].replace('-', ':');
            String[] log = logs[i].split(":");
            
            int start = 0;
            for(int j = 0; j<3; j++){
                start += Integer.parseInt(log[j]) * timeUnit[j];
            }
            
            int end = 0;
            for(int j = 3; j<6; j++){
                end += Integer.parseInt(log[j]) * timeUnit[j-3];
            }
            
            temp[start]++;
            temp[end]--;
        }
        
        int sum = 0;
        for(int i = 0; i<MAX; i++){
            sum += temp[i];
            logsTime[i] = sum;
        }
    }
    
    public String setResult(int timeLine){
        int hour = timeLine / timeUnit[0];
        timeLine -= hour * timeUnit[0];
        int minute = timeLine / timeUnit[1];
        timeLine -= minute * timeUnit[1];
        int second = timeLine;
        
        String time = "";
        if(hour < 10){
            time += ("0" + hour);
        }
        else{
            time += "" + hour;
        }
        time += ":";
        
        
        if(minute < 10){
            time += ("0" + minute);
        }
        else{
            time += "" + minute;
        }
        time += ":";
        
        if(second < 10){
            time += ("0" + second);
        }
        else{
            time += "" + second;
        }
        
        
        return time;
    }
    
    public String solution(String play_time, String adv_time, String[] logs) {
        String answer = "";
        
        String[] play_times = play_time.split(":");
        for(int i = 0; i<3; i++){
            MAX += Integer.parseInt(play_times[i]) * timeUnit[i];
        }
        MAX += 2;
 
        setLogsTime(logs);
        int timeLine = getTimeLine(adv_time);
        answer = setResult(timeLine);
        
        
        
        return answer;
    }
}