[프로그래머스,Java] Level3: 광고 삽입
https://school.programmers.co.kr/learn/courses/30/lessons/72414
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제분석
시청자의 동영상 로그를 토대로, 최적의 광고타이밍을 선정해야한다.
동영상 상영시간은 최대 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분이라고 간주를하나본다...
분단위로 짤라버려가지고 좀 많이 헤멨다.
전체풀이
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
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;
}
}
|
cs |