문제
너튜브에서 유명한 크리에이터로 활동 중인 커미는 환경 단체로부터 자신의 가장 인기있는 동영상에
지구온난화의 심각성을 알리기 위한 공익광고를 넣어 달라는 요청을 받았다.
평소에 환경 문제에 관심을 가지고 있던 커미는 요청을 받아들였고 광고효과를 높이기 위해
시청자들이 가장 많이 보는 구간에 공익광고를 넣으려고 한다.
커미는 시청자들이 해당 동영상의 어떤 구간을 재생했는지 알 수 있는 재생구간 기록을 구했고,
해당 기록을 바탕으로 공익광고가 삽입될 최적의 위치를 고를 수 있었다.
참고로 광고는 재생 중인 동영상의 오른쪽 아래에서 원래 영상과 동시에 재생되는
PIP(Picture in Picture)형태로 제공된다.
다음은 커미가 공익광고가 삽입될 최적의 위치를 고르는 과정을 그림으로 설명한 것이다.
* 그림의 파란색 선은 광고를 검토 중인 커미 동영상의 전체 재생 구간을 나타낸다.
- 위 그림에서, 커미동영상의 총 재생시간은 02시간 03분 55초이다.
* 그림의 검은색 선들은 각 시청자들이 커미의 동영상을 재생한 구간의 위치를 표시하고 있다.
- 검은색 선의 가운데 숫자는 각 재생 기록을 구분하는 ID를 나타낸다.
- 검은색 선에 표기된 왼쪽 끝 숫자와 오른쪽 끝 숫자는 시청자들이 재생한 동영상 구간의 시작
시각과 종료 시각을 나타낸다.
- 위 그림에서, 3번 재생 기록은 00시 25분 50초부터 00시 48분 29초까지
총 00시간 22분 39초 동안 커미의 동영상을 재생했다.
- 위 그림에서, 1번 재생 기록은 01시 20분 15초부터 01시 45분 14초까지
총 00시간 24분 59초 동안 커미의 동영상을 재생했다.
* 그림의 빨간색 선은 커미가 선택한 최적의 공익광고 위치를 나타낸다.
- 만약 공익광고의 재생시간이 00시간 14분 15초라면, 위의 그림처럼 01시 30분 59초부터
01시 45분 14초까지 공익광고를 삽입하는 것이 가장 좋다.
이 구간을 시청한 시청자들의 누적재생시간이 가장 크기 때문이다.
- 01시 30분59초부터 01시 45분 14초까지의 누적 재생시간은 다음과 같이 계산된다.
# 01시 30분 59초부터 01시 37분 44초 까지: 4번, 1번 재생 기록이 두차례 있으므로
재생 시간의 합은 00시간 06분 45초 * 2 = 00시간 13분 30초
# 01시 37분 44초 부터 01시 45분 14초까지 : 4번, 1번, 5번, 재생 기록이 세차례
있으므로 재생시간의 합은 00시간 07분 30초 * 3 = 00시간 22분 30초
# 따라서, 이 구간 시청자들의 누적 재생시간은
00시간 13분 30초 + 00시간 22분 30초 = 00시간 36분 00초 이다.
커미의 동영상 재생시간과, 공익광고의 재생시간 그리고
시청자들이 해당 동영상을 재생했던 구간 정보가 주어질 때,
시청자들의 누적 재생시간이 가장 많이 나오는 곳에 공익광고를 삽입하려고 한다.
이때, 공익광고가 들어갈 시작 시각을 구하는 프로그램을 작성하시오.
입력
첫행에 커미의 동영상 재생시간이 HH:MM:SS 형식의 8자리 문자열로 주어진다.
두번째 행에 공익광고 재생시간이 HH:MM:SS 형식의 8자리 문자열로 주어진다.
공익광고 재생시간은 동영상 재생시간보다 짧거나 같다.
세번째 행에 시청자들의 수 N이 주어진다. ( 1 <= N <= 300,000)
이어진 N개의 행에 시청자들이 재생했던 구간정보가
H1:M1:S1-H2:M2:S2 형식의 17자리 문자열로 주어진다.
재생시작시각과 재생종료시각이다.
재생시간 HH:MM:SS 은
00:00:01 이상 99:59:59 이하이다.
00 <= HH <= 99
00 <= MM, SS <= 59
재생시각 H1:M1:S1와 H2:M2:S2은
00:00:00 이상 99:59:59 이하이다.
00 <= H1, H2 <= 99
00 <= M1, M2, S1, S2 <= 59
잘못된 시각 및 시간은 입력으로 주어지지 않는다.
(예: 04:60:24, 11:12:78, 123:12:45 등)
출력
공익광고가 들어갈 시작 시각을 구하여 HH:MM:SS 형식의 8자리 문자열로 출력한다.
만약, 시청자들의 누적 재생시간이 가장 많은 곳이 여러 곳이라면,
그 중에서 가장 빠른 시작 시각을 출력한다.
예제 #1
02:03:55
00:14:15
5
01:20:15-01:45:14
00:40:31-01:00:00
00:25:50-00:48:29
01:30:59-01:53:29
01:37:44-02:02:30
01:30:59
예제 #2
99:59:59
25:00:00
4
69:59:59-89:59:59
01:00:00-21:00:00
79:59:59-99:59:59
11:00:00-31:00:00
01:00:00
예제 #3
50:00:00
50:00:00
3
15:36:51-38:21:49
10:14:18-15:36:51
38:21:49-42:51:45
00:00:00
힌트
출처
kakao2020_2 5번 | dnfka0930
로그인해야 코드를 작성할 수 있어요.