[Programmers] 11-1. 광고 삽입

import java.util.*; class Solution { public String solution(String play_time, String adv_time, String[] logs) { int pt = convertInt(play_time); int at = convertInt(adv_time); int log_cnt = logs.length; ArrayList<int[]> logList = new ArrayList<int[]>(); // 1. 시간값을 모두 숫자값으로 변환 for(int i=0; i<log_cnt; i++){ String[] s = logs[i].split("-"); int st = convertInt(s[0]); int et = convertInt(s[1]); int[] log = {st, et}; logList.add(log); } // 2. 시간이 빠른순으로 정렬 Collections.sort(logList, (a1,a2) -> a1[0] - a2[0]); // 3. 각 시청시간의 시작지점을 기준으로 광고배치를 했을때 가장 많이 보는경우를 구한다. int idx = 0; int cnt = 0; for(int i=0; i<log_cnt; i++){ int st = logList.get(i)[0]; int et = st + at; int temp = 0; for(int j=i; j<log_cnt; j++){ int[] log = logList.get(j); if(et < log[0]) break; // 광고 범위를 벗어난다. else if(et < log[1]) temp += et - log[0]; // 포함은 되어있으나 시청도중에 광고가 끊긴다. else temp += log[1] - log[0]; // 광고 범위안에 모든 시청시간이 포함된다. } if(cnt < temp) { cnt = temp; idx = i; } } String answer; if(logList.get(idx)[0] + at > pt){ answer = convertString(logList.get(idx)[0] - (logList.get(idx)[0] + at - pt)); } else{ answer = convertString(logList.get(idx)[0]); } return answer; } private int convertInt(String time){ String[] s = time.split(":"); return Integer.parseInt(s[0]) * 3600 + Integer.parseInt(s[1]) * 60 + Integer.parseInt(s[2]); } private String convertString(int time){ int h = time / 3600; int m = (time % 3600) / 60; int s = time % 60; return String.format("%02d:%02d:%02d", h, m, s); } }

import java.util.*; class Solution { public String solution(String play_time, String adv_time, String[] logs) { int pt = convertInt(play_time); int at = convertInt(adv_time); int log_cnt = logs.length; int[] time = new int[pt+1]; // 1. 시간값을 모두 숫자값으로 변환 (로그는 최대 30만개) for(int i=0; i<log_cnt; i++){ String[] s = logs[i].split("-"); int st = convertInt(s[0]); int et = convertInt(s[1]); time[st]++; time[et]--; } // 2. 전체 시간을 누적합으로 계산해둔다. (최대 36만개) for(int i=1; i<time.length; i++){ time[i] += time[i-1]; } // 3.가장 구간합이 큰 구간을 구한다. (최대 36만개) int answer = 0; long interval_time = 0; // long으로 선언해야 17번 태케통과함 for(int i=0; i<at; i++){ // 최초 구간합 interval_time += time[i]; } long max = interval_time; // 9, 31번이 틀렸던 이유.. (초기 max를 0으로 냅둠) for(int i=0, j=at; j<pt; i++, j++){ // 1초씩 움직이며 투포인터 계산 interval_time += time[j]; interval_time -= time[i]; if(interval_time > max){ answer = i+1; max = interval_time; } } return convertString(answer); } private int convertInt(String time){ String[] s = time.split(":"); return Integer.parseInt(s[0]) * 3600 + Integer.parseInt(s[1]) * 60 + Integer.parseInt(s[2]); } private String convertString(int time){ int h = time / 3600; int m = (time % 3600) / 60; int s = time % 60; return String.format("%02d:%02d:%02d", h, m, s); } }

import java.util.Arrays; class Solution { public String solution(String play_time, String adv_time, String[] logs) { int playTime = parseTime(play_time); int advTime = parseTime(adv_time); long playNums[] = new long[playTime+10]; for(String log : logs){ String splitted[] = log.split("-"); playNums[parseTime(splitted[0])]++; playNums[parseTime(splitted[1])]--; } for(int i = 0; i < playNums.length-1; i++) playNums[i+1] += playNums[i]; int startTime = 0; long timeSum = 0; long max = timeSum; long maxStartTime = 0; while(startTime+advTime <= playTime){ if(max < timeSum){ max = timeSum; maxStartTime = startTime; } timeSum -= playNums[startTime]; timeSum += playNums[startTime+advTime]; startTime++; } return String.format("%02d:%02d:%02d", maxStartTime/3600, (maxStartTime/60)%60, maxStartTime%60); } int parseTime(String time){ String splitted[] = time.split(":"); return Integer.parseInt(splitted[0])*3600 + Integer.parseInt(splitted[1])*60 + Integer.parseInt(splitted[2]); } }