5. 광고 삽입

처음 접해보는 슬라이딩 윈도우 기법인데 카드 짝맞추기보다 어렵지 않은 것 같다. 다만 약간의 수학(시분초 <=> 초)과 아직 익숙치 않은 문자열 파싱하는 부분이 좀 어려웠다.

  1. 슬라이딩 윈도우 기법

  2. 시,분,초 <=> 초 변환 (은근히 어려웠다(?)) 시 : 초 / 3600 분 : (초 % 3600)/60 초 : (초 % 3600)%60 = 초%60

  3. 문자열 파싱

일단, 2차원 배열을 한자리 정수로 나타내는 것처럼 발상의 전환이 있었다. 시간+분+초를 계산을 용이하게 하기 위해 초단위로 변환한다. 1시간 = 3600초, 1분 = 60초이므로 HH*3600 + MM*60 + SS로 변환해준다.

마지막에는 시간 분 초 형태로 리턴해야하기 때문에 반대로 변환해준다. 시간 = 초 / 3600, 분 = 초 / 60 % 60, 초 = 초 % 60 이 된다. 시, 분, 초 => 초로 변환했을 때와 반대로 변환하면 된다.

‼️틀린 이유‼️

분 = 초 / 60 => 60을 곱해줬기 때문에 60을 다시 나눠주면 된다고 생각했는데, 변환한 초값에서 3600으로 나눈 몫이 "시"이고, 그 나머지는 (분+초)에 해당한다. 이 나머지를 60으로 나눠준 값이 분이 된다. ex) 15시간 30분 25초 ① 시분초=>초 변환 : 15*3600 + 30*60 + 25 = 54000 + 1800 + 25= 55825초 ② 초=>시분초 변환 시 : 55825 / 3600 = 15(몫) = 15시간 분 : 55825 % 3600 = 1825(나머지 = 분+초) 이므로, (초 % 3600)/60으로 나눈 몫이 분에 해당한다!!! 초에 해당하는 값을 60만큼 묶어주어 1분단위로 나타내는 것이다! 따라서 (55825 % 3600)/60 = 1825/60 = 30분 초 : (55825%3600)/60의 나머지에 해당하기 때문에 (초%3600)%60에 해당한다.

슬라이딩 윈도우 기법 :

시분초를 초단위로 변환하고, 이 초단위 크기만큼 배열Arr을 생성해서 사용자들이 영상을 시청하는 시간에 해당하는 배열 칸에 값을 1로 설정함으로써 최대 누적 시청 구간을 구할 수 있다. (편의상 배열 인덱스1부터 사용) ex) log1 시작 시각:1, 종료 시각:12(러닝타임11) => Arr[1] = Arr[2] = ...Arr[11] = 1

문제에서 영상 길이 최대 99:59:59 이기 때문에 100시간보다 1초 작다. 따라서 3600 * 100 = 360,000 크기의 배열을 생성하여 사용자들의 log 기록을 저장할 수 있다.

구현

슬라이딩 윈도우 기법⭐️⭐️⭐️⭐️⭐️

  1. 전체 영상 시각을 의미하는 배열 totalSec을 생성한다.

  2. logs배열을 순회하며 각 log마다 시작 시각, 종료 시각을 초단위로 변경해서 배열에 그 구간에 해당하는 값들을 1 더한다. //사용자들의 로그를 totalSec에 기록. =>"재생되는 구간" 을 1씩 더해가면서 마킹하기 때문에 문제에서 주어진 예시에 따라, log가 끝나는 구간은 "재생되는 구간"에 포함되지 않는다!!

  3. 0부터 시작해서 1칸씩 오른쪽으로 이동하여 광고 길이만큼 해당하는 구간의 합산한 배열값(currSum)의 최댓값(maxSum)과 함께 이 때의 시작 인덱스(maxIdx)를 저장한다! 예를 들어, 광고 길이가 5라고 한다면 0부터 시작하면 0,1,2,3,4 가 광고 구간이다. ① 0부터 시작한 광고 구간 누적 횟수 currSum ② 오른쪽으로 1칸 이동하는 반복문 구현 =>①에 이어서 하기 때문에! 반복 변수 i = advSec(여기서는 5부터) ~ playSec(영상 전체 길이에 해당) 1칸씩 이동하면서 값을 합산할 때, 새로운 1칸 더하고, 기존의 첫번째 1칸 빼주는 식으로 갱신해나간다! => 새로운 i번째 칸 더하고, i-advSec 칸은 빼준다! ③ 최댓값 갱신 : maxSum < currSum 이면 currSum으로 갱신, 이때의 maxIdx도 함께 갱신 maxIdx = i-advSec + 1. 예를 들어 현재 i가 7일 때 최대 누적 값 갖는다면 7,6,5,4,3 이기 때문에 7-광고 길이 +1(7-5 + 1) 해주면 된다.

문자열 파싱⭐️⭐️⭐️⭐️⭐️

  1. playTime, adv_time = HH:MM:SS => split(":")으로 문자 분리하고, 리턴 타입이 String[ ] 타입이기 때문에 [0] : 시, [1] : 분, [2] : 초가 된다.

  2. 각각의 log = HH:MM:SS-HH:MM:SS 총 17 길이의 문자이다. 먼저, String의 substring을 이용하여 시작시간과 종료시간으로 분류한다. 그리고 1에서 구현한 함수로 각 시작시간과 종료시간을 초로 나타낼 수 있다.

문제에서 주어진 HH:MM:SS 형식으로 문자열 리턴하는 방법

String.format()으로 가능하다!

return String.format("%02d:%02d:%02d",
                maxIdx/3600,
                maxIdx / 60 % 60,
                maxIdx % 60);

2번째 풀었을 때 정답과 차이점

  1. 슬라이딩 윈도우 : 0번째부터 할 때

    //3.슬라이딩 윈도우
//3-1.0번째부터 시작.
long curSum=0;//광고 구간만큼의 누적 횟수 합산값 저장.
for(int i=0;i+advSec<playSec;i++){ 
    curSum += totalSec[i];
}

    정답 : 0부터 시작하기 때문에 광고 길이만큼만 반복해주어도 무관하다.

  2. //3.슬라이딩 윈도우
//3-1.0번째부터 시작.
long curSum=0;//광고 구간만큼의 누적 횟수 합산값 저장.
for(int i=0;i<advSec;i++){ 
    curSum += totalSec[i];
}

  3. 입출력 예시에서 어떤 log가 01:00:00-11:00:00 이라고 하면, 이 구간의 재생 시간은 10:00:00이라고 되어있다. 즉, start-end에서 재생 시간에 포함되는 시은 start~(end-1)까지이다. ex) 초로 변환한 start = 1, end = 12 라면 배열에 마킹할 구간은 Arr[1] = Arr[2] = Arr[3] = ...Arr[11] = 1 로서, end는 포함되지 않고 end-1번째 인덱스까지 1더해주면 된다!

  4. java에서 int 양수 범위는 최대 약 21억이다. 문제에서 제한은 영상의 길이는 약 100시간 => 약 36만개, logs의 길이는 최대 30만 이므로, 영상 전체 길이와 동일한 log가 30만개 있을 경우, 36만개의 1 X 30만 = 1080,0000,0000 = 약 천억이다. 그렇기 때문에 광고 구간의 누적 횟수를 합산한 값은 int가 아니라 long에 저장해야만 엣지케이스들도 모두 저장할 수 있다!

Previous4. 합승 택시 요금Next6. 카드 짝 맞추기

Last updated