[2021 KAKAO BLIND RECRUITMENT] 광고 삽입

[uijin-j]

🔗 광고 삽입

[hye-on]

📑 댓글 템플릿

• Language : C++
• 성능

코드 풀이

```cpp #include #include #include #include #include using namespace std; vector> t; // i~i+1구간까지 중접된 개수, 시각 priority_queue, vector>, greater>> pq; long long timeToInt(string time) { int hs = stoi(time.substr(0,2)) * 60 * 60; int ms = stoi(time.substr(3,2)) * 60; int s = stoi(time.substr(6,2)); return hs + ms + s; } string intToTime(long long num) { string st = ""; int h = num / 3600; num %= 3600; int m = num / 60; int s = num % 60; if (h <= 9) st += '0'; st += to_string(h); st += ":"; if (m <= 9) st += '0'; st += to_string(m); st += ":"; if (s <= 9) st += '0'; st += to_string(s); return st; } void insertAfterInt(string s) { string startTime = s.substr(0,8); string endTime = s.substr(9,8); pq.push({timeToInt(startTime), 0}); //0이면 시작 시각 pq.push({timeToInt(endTime), 1}); //1이면 끝 시각 } string solution(string play_time, string adv_time, vector logs) { long long playTimeInt = timeToInt(play_time); long long duration = timeToInt(adv_time); if (logs.empty() || duration >= playTimeInt) { return "00:00:00"; } for (auto lo : logs) { insertAfterInt(lo); } vector totalTime(playTimeInt + 1, 0); while (!pq.empty()) { long long time = pq.top().first; int type = pq.top().second; pq.pop(); if (type == 0) { // 시작 시간 totalTime[time]++; } else { // 종료 시간 totalTime[time]--; } } // 누적 합 계산 for (int i = 1; i <= playTimeInt; i++) { totalTime[i] += totalTime[i-1]; } // 구간 합 계산 // i까지의 합 for (int i = 1; i <= playTimeInt; i++) { totalTime[i] += totalTime[i-1]; } long long maxTime = totalTime[duration - 1]; long long ansInt = 0; for (long long i = duration; i < playTimeInt; i++) { //i까지의 합 - j까지의 합 = j-i구간 합 long long currentTime = totalTime[i] - totalTime[i - duration]; if (currentTime > maxTime) { maxTime = currentTime; ansInt = i - duration + 1; } } return intToTime(ansInt); } ```

코멘트

[uijin-j]

📑 댓글 템플릿

• Language : Java
• 성능

코드 풀이

```java import java.util.Arrays; class Solution { public String solution(String play_time, String adv_time, String[] logs) { int playSeconds = toSeconds(play_time); int advSeconds = toSeconds(adv_time); int[] watch = new int[playSeconds + 1]; // watch[i]: i ~ i+1초 사이에 영상 시청 수 for (String log : logs) { String[] splited = log.split("-"); int start = toSeconds(splited[0]); int end = toSeconds(splited[1]); for (int i = start; i < end; i++) { watch[i]++; } } long total = 0; for (int i = 0; i < advSeconds; i++) { total += watch[i]; } int maxIdx = 0; long maxTotal = total; for (int end = advSeconds; end < playSeconds; ++end) { int start = end - advSeconds + 1; total += watch[end]; total -= watch[start - 1]; if (total > maxTotal) { maxTotal = total; maxIdx = start; } } return toHHMMSS(maxIdx); } public int toSeconds(String hhmmss) { String[] info = hhmmss.split(":"); int total = 0; total += Integer.parseInt(info[0]) * 60 * 60; total += Integer.parseInt(info[1]) * 60; total += Integer.parseInt(info[2]); return total; } public String toHHMMSS(int seconds) { int h = seconds / (60 * 60); seconds = Math.max(0, seconds - h * (60 * 60)); int m = seconds / 60; seconds = Math.max(0, seconds - m * (60)); int s = seconds; String hh = (h > 9) ? String.valueOf(h) : "0" + String.valueOf(h); String mm = (m > 9) ? String.valueOf(m) : "0" + String.valueOf(m); String ss = (s > 9) ? String.valueOf(s) : "0" + String.valueOf(s); return hh + ":" + mm + ":" + ss; } } ```

코멘트

- 시초날 것 같아서.. O(n+m)으로 풀려고 했는데, 안풀려서풀이를 보니 O(nm)으로 다들 풀더라구요..! 그런데 코드를 조금만 다르게해도 바로 시간 초과가 나서 카카오가 의도한 풀이는 이게 아닌 것 같아요.!