[C++로 풀이] 광고 삽입 (구간합 Prefix Sum, 투포인터)⭐⭐⭐
카테고리: Programmers
태그: Coding Test Algorithm
📌 광고 삽입
난이도 ⭐⭐⭐
🚀 문제
🚀 내 풀이
숙지해야 할 것
- 시청 종료 시간은 시청자 수 카운팅에 포함되지 않는다고 생각한다.
- “동영상 재생시간 = 재생이 종료된 시각 - 재생이 시작된 시각(예를 들어, 00시 00분 01초부터 00시 00분 10초까지 동영상이 재생되었다면, 동영상 재생시간은 9초 입니다.” 라고 문제에서 언급 되었기 때문이다.
- 단순히 “구간이 중복되는 횟수”만 구할게 아니라 "누적 재생 시간"을 구하라고 했기 때문에 고정적인 광고 시간내에서 가장 많은 누적 재생 시간이 나오게 될 때의 그 광고 시작 시작 시간을 구해야 한다.
- 최대 재생 시간은 99시간 59분 59초이기 때문에 즉,
play_time이 가질 수 있는 최대값은 100시간이라는 것이다.(종료시간은 재생시간에 포함 안됨)- 100시간 = 360,000초 이다. 그러므로
O(360,000)시간 복잡도로 푸는 것이 좋겠다.
- 100시간 = 360,000초 이다. 그러므로
🔥 Prefix Sum 구간합으로 푼 풀이
어떤 구간의 합을 구할 때 그 구간의 모든 원소들을 일일이 더하면 O(N)이다. 그렇게 구하지 않고 이전 구간에서 새로운 구간으로 바뀌면서, 새로운 구간에 들게 되지 못한 값은 빼주고, 새로운 구간에 새롭게 들게 된 값은 더해주는 식으로 구간 합을 쉽게 O(1)으로 구할 수 있다. 이것이 바로 Prefix Sum 이다.
Sum = Sum - A + B
난 이 문제를 내 힘으로 풀지 못했다. 자꾸 막혀서 오랫동안 고민하다 포기하고 ㅠㅜ 이 유튜브로 이 문제 풀이를 이해하게 되었다. 얼마전에 투포인터, 구간합 공부해놓고는 ㅠㅠ.. 못 풀다니! 반성해야 한다.. 아무튼! 이 유튜브를 참고한 풀이임을 밝힌다. (34분대부터 참고함)
"초"별로 합이 가장 큰 시간을 찾아야한다.
8초~16초 시간대 영상 로그를 통해 8~16초 이렇게 총 9 초 길이 구간(= 9 개의 칸)에 모두 1 씩 더하고 1~3초 시간대 영상 로그를 통해 1~3초 이렇게 총 3 초 길이 구간에 모두 1 씩 더하고.. 이런식으로 1씩 더해주면 최종적으로 “시청 시간(초)당 총 시청수”가 정해지게 된다. 즉 “초당 시청 수”를 위와 같은 방식으로 구할 수 있게 된다. 이렇게 구한 결과에서 “시청 시간(초)”들의 합이 가장 큰 구간, 즉 초당 조회수가 가장 많이 나온 시간 구간을 찾으면 된다.
그러나 이렇게 “초당 시청 수”를 구하면 시간 효율성이 매우 좋지 못하다. logs 배열의 크기가 N이라고 할 때 최대 O(3600000 * N) 시간복잡도가 걸리기 때문이다.(logs배열의 최대 크기도 300,000 이라 엄청나게 큰 연산 시간이 필요할 수도 있다.) 영상에 따르면 프로그래머스에서 C++ 로 풀이할 땐 시간초과가 나지 않는다고 하는데, 사실 시간초과가 나야 정상이라고 한다.
아무튼! 위와 같이 하나의 로그마다 모든 자리(초)에 1 을 더하여 최대 초당 조회수 시간대를 구하려는 것은 추천하지 않는다.
✈ “초 당 시청자 수의 누적합”으로 광고 구간 합을 구하는 방법
모든 동영상 시청 구간의 초마다 1 을 더하지 않고, 시청 시작 시간과 종료 시간에만 각각 1 을 더해주고 1 을 빼주면 된다. 그리고 이 결과를 합산하면 “시청 시간(초)당 총 시청수”가 된다.
이 방법은 위의 방법과는 다르게 O(3600000) 로 더 빠르게 “시청 시간(초)당 총 시청수”를 구할 수 있다.
- 1️⃣ 변화량
- 시청 시작 시간에는 1 을 더하고, 종료 시간에는 -1 을 빼준다.
- 이렇게 전부 해주고나면 예를 들어 2가 된다면 그 이전 초, 즉 1 초 전보다 시청수가 2 늘었다는 변화량을 의미하게 된다.
- -1 이라는 것은 앞 칸인 1 초 전보다 시청수가 1 만큼 줄었다는 것이다. 종료 시간은 시청 수에 카운팅 되지 않기 떄문에 이렇게 종료 시간에 감소를 표현하는 -1 을 체크한다.
- 시청 시작 시간에는 1 을 더하고, 종료 시간에는 -1 을 빼준다.
- 2️⃣ 초 당 시청수
- 앞서 구한 “변화량”을 누적합 하여 초당 시청 수를 구한다.
- 변화량을 모두 더하니 해당 초의 시청 수가 완성되게 된다.
- O(3600000 * N) 으로 동영상 시청구간마다 모두 1을 더해줄 필요 없이 이렇게 O(360000) 으로 1) 시작, 종료 시간 양끝에 1, -1 만 더하여
delta변화량을 기록 해준 후 2) 차례대로 합산하여 “초당 시청수”로 만들면 된다.- 시간 복잡도를 줄이기 위해 1️⃣ -> 2️⃣ 과정을 거쳐서 “초당 시청수”를 구하는 것이다.
- 3️⃣ 초 당 시청수 누적 합
- “누적 시청자수 합이 최대가 되는 광고 길이의 구간”을 구하기 위해 먼저 2️⃣까지 구한 “초당 시청수”를 차례대로 더해 누적 합한다.
- 4️⃣ 광고 구간 합⭐ (여기서 최대값이 바로 답이 됨)
- 3️⃣에서 구한 초당 시청수 누적합으로 광고 길이만큼의 누적 시청수를 구한다.
- 예를 들어 12초의 광고 구간 합은 12,13,14 이렇게 3초 동안의 누적 시청수를 의미한다.
- 광고 구간 합을 A, 초당 시청 수 누적 합을 S 라고 하면
- A[0] = S[광고시간 - 1] (그림에서 진한 보라색)
- 예를 들어 광고 시간이 3 초일 때, 0 초에서 시작한 광고 시간 동안의 누적 시청수 A[0]는 0 ~ 2 초 동안의 누적합인 S[2] 가 되어야 한다.
- A[i] = S[i + 광고시간 - 1] - S[i - 1] (그림에서 연한 보락색들)
i초에서 시작하는 광고 시간동안의 누적 시청자수는 0초부터i + 광고시간 - 1초 까지의 누적합에서 0초부터i - 1초 까지의 누적합을 빼주면 구할 수 있다.- 예를 들어 광고 시간이 3 초 일 때, 12 초에서 시작하는 광고 시간동안의 누적 시청자수 A[12]는 0~14초까지의 누적합인 S[14] 에서 0~11초까지의 누적합인 S[11]을 빼면 구할 수 있다.
- A[0] = S[광고시간 - 1] (그림에서 진한 보라색)
- 광고 구간 합을 A, 초당 시청 수 누적 합을 S 라고 하면
- 광고 구간합을 구하는 것도 2️⃣ 초당 시청수를 가지고 A[3] = V[3] + V[4] + V[5] 이런식으로 일일이 다 더해서 구했다면 최대 \(O(360000^2)\) 시간 복잡도가 발생할 것이다. 이렇게 한번 3️⃣누적합 을 진행해준 후 이걸 가지고 광고 구간합을 구하면 O(360000)으로 구할 수 있다.
- 이 모든 광고 구간 합 중 최대가 되는 것(중에서도 가장 왼쪽)에 위치하는 시간을 찾으면 된다.
- 1️⃣ 변화량 : D
- 2️⃣ 초 당 시청수 : V
- 3️⃣ 초 당 시청수 누적합 : S
- 4️⃣ 광고 시작 시간 당 시청수 누적합 : A
- i = 0 👉 A[0] = S[광고시간 - 1]
- i != 0 👉 A[i] = S[i + 광고시간 - 1] - S[i - 1]
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// 문자열 시간을 초 단위의 int 정수로 변환
int ToInt(string log) {
int hours = stoi(log.substr(0, 2));
int minutes = stoi(log.substr(3, 2));
int seconds = stoi(log.substr(6, 2));
return 3600 * hours + 60 * minutes + seconds;
}
// 초 단위의 int 정수를 문자열 시간으로 변환
string ToStr(int log) {
string hours = to_string(log / 3600);
if (hours.length() == 1) hours = "0" + hours;
string minutes = to_string((log % 3600) / 60);
if (minutes.length() == 1) minutes = "0" + minutes;
string seconds = to_string((log % 3600) % 60);
if (seconds.length() == 1) seconds = "0" + seconds;
return hours + ":" + minutes + ":" + seconds;
}
string solution(string play_time, string adv_time, vector<string> logs) {
string answer = "";
int playTotalTime = ToInt(play_time); // 동영상 전체 시간 (초 단위 정수)
int advTotalTime = ToInt(adv_time); // 광고 재생 시간 (초 단위 정수)
vector<long long> views(playTotalTime + 1); // 인덱스를 "초"에 대응시킴
// 1️⃣ 변화량
for (auto& log : logs) { // 시청 시간 로그마다
int startTime = ToInt(log.substr(0, 8));
views[startTime]++; // views[시청시작시간] 에 1 더하기
int endTime = ToInt(log.substr(9, 8));
views[endTime]--; // views[시청종료시간] 에 1 빼기
}
// 2️⃣ 초 당 시청수 (= 1️⃣변화량 누적 합산)
for (int time = 1; time <= playTotalTime; ++time)
views[time] += views[time - 1];
// 3️⃣ 초 당 시청수 누적합 (= 2️⃣초 당 시청수 누적 합산)
for (int time = 1; time <= playTotalTime; ++time)
views[time] += views[time - 1];
// 4️⃣ 광고 시작 시간 당 시청수 누적합
long long sumViews = views[advTotalTime - 1]; // 0초에 시작하는 광고의 시청수 누적합은 0 ~ (광고시간-1)초 동안의 시청자수 누적합
long long maxViews = sumViews; // 광고 시작 시간 당 시청수 누적합 中 최대값 저장
int answerTime = 0; // // 광고 시작 시간 당 시청수 누적합 中 최대값이 등장하는 광고 시작 시간 저장
for (int time = 1; time <= playTotalTime - advTotalTime; ++time) { // 광고 시작 시간 0초는 바로 위에서 구해놨고, 광고 시작 시간이 가질 수 있는 최대값은 (종료시간 - 광고시간) 시간이다. 동영상 종료시간을 넘어서 재생할 순 없으니까.
sumViews = views[time + advTotalTime - 1] - views[time - 1]; // A[i] = S[i + 광고시간 - 1] - S[i - 1]
if (maxViews < sumViews) {
maxViews = sumViews; // 광고 시작 시간 당 시청수 누적합 中 최대값 저장
answerTime = time; // // 광고 시작 시간 당 시청수 누적합 中 최대값이 등장한 시간을 답으로 제출해야 하므로 시간도 저장
}
}
answer = ToStr(answerTime); // 정답 시간을 문자열로 변환 후 제출
return answer;
}
오버플로우 고려하는 습관 들이기
2️⃣3️⃣을 통해 시청자수를 계속 누적합 하기 때문에 int 표현 범위를 넘어선 크기(약 21억)의 정수까지 도달할 수도 있다. 그러니 시청자수와 관련된 변수들을 모두 long long으로 선언을 해준다. long long으로 선언하지 않으면 오버플로우 때문인지 몇몇 테스트케이스는 통과되지 못했다.
정수는 꼭 int여야 한다는 생각을 버리고!!! 입력 크기가 상당하고 합산을 계속 하는 작업이라면!!! 더 큰 자료형 long long을 고려하기!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 정말 정말 정말 중요한 부분이다!!!!!! 틀리는 이유가 오버플로우 때문일 수도 있다!!!!!!!!!!!!!!!!!
✈ “초 당 시청자 수”로 광고 구간 합을 구하는 방법
아래와 같은 방법으로 2️⃣ 만으로 3️⃣ 을 구할 수도 있다.
- 1️⃣ 변화량
- 시청 시작 시간에는 1 을 더하고, 종료 시간에는 -1 을 빼준다.
- 2️⃣ 초 당 시청수
- 앞서 구한 “변화량”을 누적합 하여 초당 시청 수를 구한다.
- 3️⃣ 광고 구간 합⭐ (여기서 최대값이 바로 답이 됨)
- 2️⃣ 초 당 시청수로 광고 길이만큼의 누적 시청수를 구한다.
- 광고 구간 합을 A, 초당 시청 수를 V 라고 하면
- A[0] = V[0] + V[1] +..+ V[광고시간 - 1] (그림에서 진한 보라색)
- 예를 들어 광고 시간이 3 초일 때, 0 초에서 시작한 광고 시간 동안의 누적 시청수 A[0]는 0 ~ 2 초 동안의 시청수인 V[0] + V[1] + V[2] 가 되어야 한다.
- A[i] = A[i - 1] - V[i - 1] + V[i + 광고시간 - 1] (그림에서 연한 보락색들)
- 해당하는 시청 수를 일일이 모두 더해줄 필요 없이(이러면 시간복잡도 상승..) 슬라이딩 윈도우 알고리즘처럼 광고시간만큼의 창문이 이동되면서 기존 합에서 광고 시간에 해당되지 않는 시청 수는 빠지고
- V[i - 1], 새로 창문에 들어온 시청 수는 ` + V[i + 광고시간 - 1]더해주면 된다. 이러면 일일이 더해줄 필요 없이 합을 한번 구할 떄sum - a + b` 방식으로 구하므로 O(1)로 구할 수 있게 된다. - 예를 들어 광고 시간이 3 초 일 때, 12 초에서 시작하는 광고 시간동안의 누적 시청자수 A[12]는 12 ~ 14초 동안의 광고 시청자수이기 때문에, 11 ~ 13초 동안의 광고 시청자수인 A[11] 에서 구간에서 벗어난 11초의 시청자수 V[11] 를 빼주고, 새로 구간에 들어오게 된 14초의 시청자수 V[14] 를 더해주면 된다.
- 해당하는 시청 수를 일일이 모두 더해줄 필요 없이(이러면 시간복잡도 상승..) 슬라이딩 윈도우 알고리즘처럼 광고시간만큼의 창문이 이동되면서 기존 합에서 광고 시간에 해당되지 않는 시청 수는 빠지고
- A[0] = V[0] + V[1] +..+ V[광고시간 - 1] (그림에서 진한 보라색)
- 광고 구간 합을 A, 초당 시청 수를 V 라고 하면
- 광고 구간합을 구하는 것도 A[3] = V[3] + V[4] + V[5] 이런식으로 일일이 다 더해서 구했다면 최대 \(O(360000^2)\) 시간 복잡도가 발생할 것이다.
A[0]을 구하는 처음에만 일일이 합을 다 더해sum을 구하고- 그 이후에는
sum = sum - a + b방식으로 합을 구할 때O(1)으로 구하도록 하여 총 O(360000) 을 넘지 않도록 하는게 핵심이다. (C++) 투포인터 알고리즘, 슬라이딩 윈도우 알고리즘 에서도 언급한적이 있는 방법이다!
- 2️⃣ 초 당 시청수로 광고 길이만큼의 누적 시청수를 구한다.
- 1️⃣ 변화량 : D
- 2️⃣ 초 당 시청수 : V
- 3️⃣ 광고 시작 시간 당 시청수 누적합 : A
- i = 0 👉 A[0] = V[0] + V[1] +..+ V[광고시간 - 1]
- i != 0 👉 A[i] = A[i - 1] - V[i - 1] + V[i + 광고시간 - 1]
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int ToInt(string log) {
int hours = stoi(log.substr(0, 2));
int minutes = stoi(log.substr(3, 2));
int seconds = stoi(log.substr(6, 2));
return 3600 * hours + 60 * minutes + seconds;
}
string ToStr(int log) {
string hours = to_string(log / 3600);
if (hours.length() == 1) hours = "0" + hours;
string minutes = to_string((log % 3600) / 60);
if (minutes.length() == 1) minutes = "0" + minutes;
string seconds = to_string((log % 3600) % 60);
if (seconds.length() == 1) seconds = "0" + seconds;
return hours + ":" + minutes + ":" + seconds;
}
string solution(string play_time, string adv_time, vector<string> logs) {
string answer = "";
int playTotalTime = ToInt(play_time);
int advTotalTime = ToInt(adv_time);
vector<long long> views(playTotalTime + 1);
// 1️⃣ 변화량
for (auto& log : logs) {
int startTime = ToInt(log.substr(0, 8));
views[startTime]++;
int endTime = ToInt(log.substr(9, 8));
views[endTime]--;
}
// 2️⃣ 초 당 시청수 (= 1️⃣변화량 누적 합산)
for (int time = 1; time <= playTotalTime; ++time)
views[time] += views[time - 1];
// 3️⃣ 광고 시작 시간 당 시청수 누적합
long long sumViews = 0;
long long maxViews = 0;
int answerTime = 0;
for (int time = 0; time < advTotalTime; ++time) // i = 0 👉 A[0] = V[0] + V[1] +..+ V[광고시간 - 1]
sumViews += views[time];
maxViews = sumViews;
for (int time = 1; time <= playTotalTime - advTotalTime; ++time) { // i != 0 👉 A[i] = A[i - 1] - V[i - 1] + V[i + 광고시간 - 1]
sumViews = sumViews - views[time - 1] + views[time + advTotalTime - 1]; // Prefix SUm
if (maxViews < sumViews) {
maxViews = sumViews;
answerTime = time;
}
}
answer = ToStr(answerTime);
return answer;
}
🔥 투포인터 알고리즘으로 풀이 (+Prefix Sum)
이 풀이 또한 이 영상에서 배웠다. (41분 참고) 하얀 배경의 캡처들은 위 영상 출처! 코드 또한 위 영상 출처이다.(변수명만 내가 바꿨다.)
- 🔥첫번째 풀이와 다른 점이 있다면
- 🔥첫번째 풀이
- 시간(초) 단위.
- O(360000) 👉
logs의 크기와 상관없이 동영상 종료 시간 전의 모든 시간(초)를 순회하기 때문에
- 🔥투포인터 풀이
- 구간의 시작과 끝, 즉 이벤트 단위.
- O(n) 👉
logs의 크기에 비례한다. 로그마다 시작, 종료 이벤트를 체크하며 그 이벤트에 걸릴 때를 기준으로 이동하며 순회하기 때문이다. 순회시 다음 시간(1초 뒤)로 이동하는 것이 아닌 제일 가까운 다음 이벤트의 시간으로 이동.- 이 문제에서는 최대 시간이 100 시간(360000초)였기 때문에 Prefix Sum 사용이 괜찮았지만 만약 최대 시간의 크기가 아주아주 컸다면 시간복잡도가
logs크기를 따르는 투포인터로 풀이를 하는게 좋았을 것이다.
- 이 문제에서는 최대 시간이 100 시간(360000초)였기 때문에 Prefix Sum 사용이 괜찮았지만 만약 최대 시간의 크기가 아주아주 컸다면 시간복잡도가
- 🔥첫번째 풀이
두 포인터가 가리키는 현재 두 개의 이벤트 중, 현재의 광고 구간과 가장 가까운 이벤트로 이동하며 누적 시청자수는 구간의 변경으로 발생한 Sum = Sum - A + B 을 사용하여 구해주면 된다.
- 1️⃣ 이벤트 추가 : { 시간, 변화량 }을
pair로 배열에 추가- 이벤트는 변화 지점
- { 시청 시작 시간, 1 }
- { 시청 종료 시간, -1 }
- { 0, 0 }도 넣어준다. (동영상 시작 시간인 0 초도 광고가 재생될 수 있는 시간이므로 이벤트나 마찬가지.)
- 이벤트는 변화 지점
-
2️⃣ 이벤트 배열을 시간별로 정렬
- 이런식으로 시간 별로 정렬을 해준다.
-
사실 이 정렬때문에 정확히는 O(n)이 아니라 O(nlogn) 이 된다.
- 3️⃣ 이벤트 단위로 순회하며 시청자수 구하기
- (1) {0초 이벤트} 즉, 0초에서 광고가 시작될 때의 광고 시간 동안의 누적 시청자 수 구하기
-
광고가 0 초에 시작한다면 이 광고 시간 동안의 시청자 수 구하기! 먼저 광고 시간 전에 등장하는 이벤트들마다 시청자 수를 합산하고, 광고 시간이 끝나기전에 아직 끝나진 않고 진행 중인 이벤트가 있다면 그 차이의 시청자 수를 마지막으로 더해주면 된다.
- 🔥Prefix Sum 에서는 이를 0,0,2,2,2,2 로 기록하여 누적합 or 구간합 하였겠지만 이렇게 🔥투포인터 풀이에서는 (이벤트 지점의 시청자 수 x 시간 차이) = 해당 시간 동안의 시청자 수의 합산으로 해당 광고 시간 동안의 누적 시청자 수를 구할 수 있게 된다. 그래서 2 x 0 + 4 x 2 로 구할 수 있게 된다. (광고 길이는 6이라고 가정한다. 광고 길이는 고정적임을 인지하기)
- 먼저 광고 시간 전에 등장하는 이벤트들마다 시청자 수를 합산
- 광고 시간은 6 초라고 가정한다. 그림에서 표시한 1,2,3,4 이벤트를 통하여 0 초에서 광고 시작할 때 광고 끝나기 전에 등장하는 이벤트들로 시청자 수를 구한다. (노란색)
- (이벤트2 - 이벤트1) 시간간격 * 초당 시청자 수
- (이벤트3 - 이벤트2) 시간간격 * 초당 시청자 수
- (이벤트4 - 이벤트3) 시간간격 * 초당 시청자 수
- 마찬가지로 초당 시청자 수는 변화량을 더해 알아낼 수 있다.
- 광고 시간은 6 초라고 가정한다. 그림에서 표시한 1,2,3,4 이벤트를 통하여 0 초에서 광고 시작할 때 광고 끝나기 전에 등장하는 이벤트들로 시청자 수를 구한다. (노란색)
- 아직 이벤트가 걸리진 않았지만 0 초부터 시작한 광고에 진행 중인 이벤트가 있을 수 있으므로 광고시간과 마지막 이벤트 사이에서 발생한 시청자 수도 합산해준다.(갈색)
- (광고시간 - 이벤트4) 시간간격 * 초당 시청자 수
-
-
(2) 가까운 이벤트에 걸릴 때 마다 광고 시간 동안의 누적 시청자 수 구하기 👉 Sum = Sum - A + B
- 0 초 이벤트가 아닐 때, 즉 원래
logs에 기록된 시청 시간대에서 구해보도록 하자. 슬라이딩 윈도우 생각하면서현재 광고 구간(고정된 길이)에서 "가장 가까운 이벤트"에 걸리도록 "가장 가까운 이벤트와의 시간 차이"만큼 이동을 하고, Sum = Sum - A + B 를 생각하며 구간에서 벗어난 것은 빼주고 구간에 새로 들어오게된 것은 더해주는 식으로 구해나가면 된다.
- 현재 광고 구간에서 가장 가까운 이벤트로 이동한다.
- 파란색 별(이벤트 포인터 1)과 현재의 광고 시작 시간간의 차이가 1
- 초록색 별(이벤트 포인터 2)과 현재의 광고 종료 시간간의 차이가 1
- 둘 다 같으므로 이벤트 포인터 1 위치에서 광고가 시작되도록 “파란색 별(이벤트 포인터 1)과 현재의 광고 시작 시간” 간격만큼만 광고 구간을 이동시킨다.
- 이동하면서 파란색 시청자수는 빠지고 노란색 시청자수는 새로 더해진다. 이렇게 새로운 광고 구간(하얀 화살표 + 노란 화살표)의 누적 시청자수가 완성된다.
- 0 초 이벤트가 아닐 때, 즉 원래
- 현재 광고 구간에서 가장 가까운 이벤트로 이동한다.
- 파란색 별(이벤트 포인터 1)과 현재의 광고 시작 시간간의 차이가 1
- 초록색 별(이벤트 포인터 2)과 현재의 광고 종료 시간간의 차이가 0
- 초록색 별이 현재 광고 구간에 더 가까우므로 이벤트 포인터 2 위치에서 광고가 종료되도록 “초록색 별(이벤트 포인터 2)과 현재의 광고 종료 시간” 간격만큼만 광고 구간을 이동시킨다.
- 이동하면서 파란색 시청자수는 빠지고 노란색 시청자수는 새로 더해진다. 이렇게 새로운 광고 구간(하얀 화살표 + 노란 화살표)의 누적 시청자수가 완성된다.
- 이동한 간격이 0 밖에 안되서 값이 달라지진 않았다.
- 현재 광고 구간에서 가장 가까운 이벤트로 이동한다.
- 파란색 별(이벤트 포인터 1)과 현재의 광고 시작 시간간의 차이가 1
- 초록색 별(이벤트 포인터 2)과 현재의 광고 종료 시간간의 차이가 1
- 둘 다 같으므로 이벤트 포인터 1 위치에서 광고가 시작되도록 “파란색 별(이벤트 포인터 1)과 현재의 광고 시작 시간” 간격만큼만 광고 구간을 이동시킨다.
- 이동하면서 파란색 시청자수는 빠지고 노란색 시청자수는 새로 더해진다. 이렇게 새로운 광고 구간(하얀 화살표 + 노란 화살표)의 누적 시청자수가 완성된다.
- 현재 광고 구간에서 가장 가까운 이벤트로 이동한다.
- 파란색 별(이벤트 포인터 1)과 현재의 광고 시작 시간간의 차이가 2
- 초록색 별(이벤트 포인터 2)과 현재의 광고 종료 시간간의 차이가 0
- 초록색 별이 현재 광고 구간에 더 가까우므로 이벤트 포인터 2 위치에서 광고가 종료되도록 “초록색 별(이벤트 포인터 2)과 현재의 광고 종료 시간” 간격만큼만 광고 구간을 이동시킨다.
- 이동하면서 파란색 시청자수는 빠지고 노란색 시청자수는 새로 더해진다. 이렇게 새로운 광고 구간(하얀 화살표 + 노란 화살표)의 누적 시청자수가 완성된다.
- 이동한 간격이 0 밖에 안되서 값이 달라지진 않았다.
- 현재 광고 구간에서 가장 가까운 이벤트로 이동한다.
- 파란색 별(이벤트 포인터 1)과 현재의 광고 시작 시간간의 차이가 2
- 초록색 별(이벤트 포인터 2)과 현재의 광고 종료 시간간의 차이가 2
- 둘 다 같으므로 이벤트 포인터 1 위치에서 광고가 시작되도록 “파란색 별(이벤트 포인터 1)과 현재의 광고 시작 시간” 간격만큼만 광고 구간을 이동시킨다.
- 이동하면서 파란색 시청자수는 빠지고 노란색 시청자수는 새로 더해진다. 이렇게 새로운 광고 구간(하얀 화살표 + 노란 화살표)의 누적 시청자수가 완성된다.
- (1) {0초 이벤트} 즉, 0초에서 광고가 시작될 때의 광고 시간 동안의 누적 시청자 수 구하기
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
#define time first
#define deltaView second
int ToInt(string log) {
int hours = stoi(log.substr(0, 2));
int minutes = stoi(log.substr(3, 2));
int seconds = stoi(log.substr(6, 2));
return 3600 * hours + 60 * minutes + seconds;
}
string ToStr(int log) {
string hours = to_string(log / 3600);
if (hours.length() == 1) hours = "0" + hours;
string minutes = to_string((log % 3600) / 60);
if (minutes.length() == 1) minutes = "0" + minutes;
string seconds = to_string((log % 3600) % 60);
if (seconds.length() == 1) seconds = "0" + seconds;
return hours + ":" + minutes + ":" + seconds;
}
string solution(string play_time, string adv_time, vector<string> logs) {
string answer = "";
int playTotalTime = ToInt(play_time);
int advTotalTime = ToInt(adv_time);
vector<pair<int, int>> event; // 이벤트들을 저장할 배열
event.push_back({ 0, 0 }); // 0 초도 이벤트로서 추가해주기
for (auto& log : logs) {
int startTime = ToInt(log.substr(0, 8));
event.push_back({ startTime, 1 }); // 시작 시간은 변화량 1 로 함께 저장
int endTime = ToInt(log.substr(9, 8));
event.push_back({ endTime, -1 }); // 종료 시간은 변화량 -1 로 함께 저장
}
// 시간 순서별로 정렬해주기
sort(event.begin(), event.end());
int startIndex = 0, endIndex = 0; // ⭐투포인터⭐ 파란색 별(이벤트 포인터 1), 초록색 별(이벤트 포인터 2)
long long startViews = 0, endViews = 0; // 새로운 구간에서 빠지는 시청자수(파란색), 새로운 구간에 포함되는 시청자수(노란색)
long long sumViews = 0, maxViews = 0; // 현재 광고 구간의 누적 시청자수, 현재까지 구한 광고 구간의 누적 시청자수 최대값
int advStartTime = 0, answerTime = 0; // 광고 시작 시간(매번 이벤트 시간이 대입될 것이다. 1초씩++ 되던 첫번째 풀이와 달리!), 현재까지 구한 광고 구간의 누적 시청자수 최대값이 나온 그 광고 시작 시간(답)
/* 1. {0초 이벤트} 즉, 0초에서 광고가 시작될 때의 광고 시간 동안의 누적 시청자 수 구하기 */
// 먼저 광고 시간 전에 등장하는 이벤트들마다 시청자 수를 합산
while(endIndex + 1 < event.size() && event[endIndex + 1].time <= advTotalTime) {
int deltaTime = event[endIndex + 1].time - event[endIndex].time;
sumViews += deltaTime * endViews;
endViews += event[endIndex + 1].deltaView;
endIndex++;
}
// 아직 이벤트가 걸리진 않았지만 0 초부터 시작한 광고에 진행 중인 이벤트가 있을 수 있으므로 광고시간과 마지막 이벤트 사이에서 발생한 시청자 수도 합산해준다.(갈색)
// 이부분은 사실 영상에서 등장한 코드로는 sumViews += (advTotalTime - event[endIndex + 1].time) * endViews; 이었는데 event[endIndex]이 아닌 event[endIndex + 1] 인게 이해가 잘 안됐다. 내가 생각한대로 event[endIndex] 를 사용해서 제출했는데도 다 정답 처리 되길래 이걸 사용했다. 아무튼 영상의 코드와 다른점은 여기 뿐이다.
sumViews += (advTotalTime - event[endIndex].time) * endViews;
maxViews = sumViews;
/* 2. 가까운 이벤트에 걸릴 때 마다 광고 시간 동안의 누적 시청자 수 구하기 👉 Sum = Sum - A + B */
while (advStartTime <= playTotalTime - advTotalTime && endIndex + 1 < event.size()){
//현재 광고 구간에서 가장 가까운 이벤트로 이동한다.
int startDeltaTime = event[startIndex + 1].time - advStartTime; // 파란색 별(이벤트 포인터 1)과 현재의 광고 시작 시간(advStartTime)간의 차이
int endDeltaTime = event[endIndex + 1].time - (advStartTime + advTotalTime); // 초록색 별(이벤트 포인터 2)과 현재의 광고 종료 시간(advStartTime + advTotalTime)간의 차이
if (startDeltaTime <= endDeltaTime) { // startIndex 가 가리키는 이벤트와 더 가깝다면 광고 구간을 startDeltaTime 만큼 이동한다. 그리고 Prefix Sum 으로 새로운 구간 합을 구한다.
sumViews += (endViews - startViews) * startDeltaTime; // Prefix SUm
startViews += event[startIndex + 1].deltaView; // 다음에 빠질 시청자수 (변화량 반영하여 업데이트)
startIndex++;
advStartTime += startDeltaTime; // 광고 구간 이동
}
else {
sumViews += (endViews - startViews) * endDeltaTime; // Prefix SUm
endViews += event[endIndex + 1].deltaView; // 다음에 포함될 시청자수 (변화량 반영하여 업데이트)
endIndex++;
advStartTime += endDeltaTime; // 광고 구간 이동
}
if (maxViews < sumViews){
maxViews = sumViews;
answerTime = advStartTime;
}
}
answer = ToStr(answerTime);
return answer;
}
🚀 문자열 파싱, 문자열로 변환시 유용하게 쓸 수 있는 함수
🔥 문자열 스트림 stringstream (파싱)
// 문자열 시간을 초 단위의 int 정수로 변환
int ToInt(string log) {
int hours, minutes, seconds;
char temp;
istringstream iss(log);
iss >> hours >> temp >> minutes >> temp >> seconds;
return 3600 * hours + 60 * minutes + seconds;
}
굳이 substr과 stoi 함수를 사용하지 않더라도 이렇게 문자열 스트림을 사용하여 알아서 타입에 맞게 입력할 수 있다. 꼭 공백으로만 나눌 수 있는 것은 아니고 이 예제처럼 각 데이터 타입에 맞게 나눌 수도 있다! 유용하게 잘 사용하자.
"05"가 int 정수로서5로hours에 입력된다.:가 char 로서temp에 입력된다."12"가 int 정수로서12로minutes에 입력된다.:가 char 로서temp에 입력된다."48"가 int 정수로서48로seconds에 입력된다.:가 char 로서temp에 입력된다.
참고하기 https://ansohxxn.github.io/cpp/chapter18-3/
🔥 sprintf 로 원하는 형식으로 문자열 저장하기
// 초 단위의 int 정수를 문자열 시간으로 변환
string ToStr(int log) {
char c_time[20];
sprintf(c_time, "%02d:%02d:%02d", log / 3600, log / 60 % 60, log % 60); // HH:MM:SS 형식
string time = c_time;
return time;
}
sprintf함수를 사용하여 C스타일인 char 배열에 원하는 형식대로 문자열을 저장한다.- printf 함수 사용하듯이!
- 그리고 이 char 배열을
string에 대입하면 땡이다.
참고하기 https://ansohxxn.github.io/c/2/
🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄
댓글 남기기