문제 설명 및 제한사항
아이디어 및 해결 방법
코드
from bisect import bisect_left, bisect_right
from collections import defaultdict, namedtuple
Interval = namedtuple('Interval', ['start', 'end', 'weight'])
NOTHING, START, END = 0, 1, 2
def h2s(t):
tokens = t.split(':')
return 3600*int(tokens[0]) + 60*int(tokens[1]) + int(tokens[2])
def s2h(t):
return f'{t//3600:02}:{(t%3600)//60:02}:{(t%3600)%60:02}'
def solution(play_time, adv_time, logs):
if play_time == adv_time:
return '00:00:00'
# 시간 구간을 잘 조각내서, 그 안에 몇 개의 interval이 있는지 기록해둡니다.
play_time, adv_time = h2s(play_time), h2s(adv_time)
timepoints, candidate_intervals = [], []
candidate_intervals.append((0, adv_time))
for id, log in enumerate(logs, 1):
start, end = log.split('-')
start, end = h2s(start), h2s(end)
timepoints.append((start, START, id))
timepoints.append((end, END, id))
timepoints.append((start + adv_time, NOTHING, id))
timepoints.append((end - adv_time, NOTHING, id))
candidate_intervals.append((start, start + adv_time))
candidate_intervals.append((end - adv_time, end))
timepoints.append((0, NOTHING, 0))
timepoints.append((0 + adv_time, NOTHING, 0))
timepoints.append((play_time - adv_time, NOTHING, 0))
timepoints.append((play_time, NOTHING, 0))
candidate_intervals.append((play_time - adv_time, play_time))
timepoints = [(t, flag, id) for t, flag, id in timepoints if 0 <= t <= play_time]
timepoints.sort()
candidate_intervals = [(s, e) for s, e in candidate_intervals if 0 <= s and e <= play_time]
candidate_intervals.sort()
i, prev_t, nintervals, intervals = 1, 0, 0, []
while i < len(timepoints):
t, flag, id = timepoints[i]
if t > prev_t:
intervals.append( Interval(prev_t, t, (t-prev_t) * nintervals) )
prev_t = t
if flag == START:
nintervals += 1
elif flag == END:
nintervals -= 1
i += 1
intervals.append( Interval(play_time, play_time, 0) )
mx, answer = -1, 0
lsum = 0
l, r = 0, 0
for adv_start, adv_end in candidate_intervals:
while r < len(intervals):
if intervals[r].start == adv_end:
break
lsum += intervals[r].weight
r += 1
while l < len(intervals):
if intervals[l].start == adv_start:
break
lsum -= intervals[l].weight
l += 1
if lsum > mx:
mx, answer = lsum, adv_start
return s2h(answer)
Python
복사
출처
프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges