최근 느리게 갱신되는 세그먼트 트리(lazyprop)를 공부하기 시작했다.
lazyprop 문제 중 아주 쉬운 편에 속하지만 푼 사람은 많이 없는 문제를 풀이를 해볼까 한다.
BOJ 2835 - 인기도 조사 링크
(2022.09.23 기준 P4)
(치팅하면 인기도 낮아짐)
문제
N명의 사람이 TV를 시청한 시간의 구간이 주어진다면, 어떤 초의 인기도는 그 초에 티비를 보고 있던 사람의 수가 된다. 또, 구간의 인기도는 구간에 포함되는 초의 인기도의 합을 그 구간의 길이로 나눈 값이다.
Q개의 구간이 주어질 때, 각 구간마다의 인기도를 출력.
알고리즘
구간의 합을 구해야 한다는 점에서 일단 세그먼트 트리. 그런데 TV 시청 구간이 주어질 때마다, 그 구간에 포함되는 초의 인기도를 전부 1씩 올려야 하므로 일반 세그먼트 트리로 구현하면 시간 초과가 난다.
그러므로 느리게 갱신되는 세그먼트 트리(Segment Tree with Lazy Propagation)를 사용해야 한다.
풀이
일단 lazyprop의 알고리즘을 공부하고 오자.
BOJ BOOK에 언어별로 정말 잘 설명되어 있으니 참고하자.일단 구간의 인기도는 구간에 포함되는 초의 인기도의 합을 그 구간의 길이로 나눈 값이다. 그러면 구간에 포함되는 초 별로 인기도가 있다는 말이 되고, 하루를 초 단위로 나눠야 한다는 말이 된다.
하루는 24 * 60 * 60 = 86,400초
그러면 tree와 lazy를 (1 << (ceil(log2(86400)) + 1)) 크기로 만들어 주자.
arr는 따로 하지 않아도 된다. 어차피 처음에 모든 초의 인기도는 0이기 때문.그리고 이제 N개와 Q개만큼 구간을 입력 받는다. 이 때 구간은 'HH:MM:SS - HH:NN:SS' 형태로 들어오는데, 시작과 끝을 각각 초로 반환하는 함수를 만들어주자.
def time(HMS): # HH:MM:SS를 초로 반환 H, M, S = map(int, HMS.split(':')) return (H * 60 + M) * 60 + S left, right = map(lambda x: time(x), input().split(' - ')) # 구간을 초 단위로 바꿔서 저장함수까지 만들었으면 구간을 입력 받자.
left와 right가 입력이 되면 이제부터 잘 살펴야 한다.만약에 평범하게 left <= right가 되면
left와 right를 포함하는 빨간 구간을 다루면 된다.
하지만 right < left가 된다면..?
각 양 끝점을 포함한 빨간 구간 두 개를 다뤄야 한다.
그러면 update는 그렇게 하면 되고 query도 그렇게 하면 되는데
조금만 더 최적화를 하자면, query는 양 끝 점을 포함하지 않는 파란 구간을 구해서 총 인기도의 합에서 빼면 된다. 그러면 빨간 구간 두 개 값과 같으며 query를 한 번만 호출하기 때문에 시간면에서도 이득이 된다.
전체 인기도는, N개의 구간을 입력받으며 update를 할 때, 구간의 길이만큼 더하면 구해진다.나머지는 뭐, 여느 lazyprop 문제와 같다.
코드
import sys; input = sys.stdin.readline
from math import ceil, log2
def time(HMS): # HH:MM:SS를 초로 반환
H, M, S = map(int, HMS.split(':'))
return (H * 60 + M) * 60 + S
def update_lazy(node, start, end):
if lazy[node]:
tree[node] += (end - start + 1) * lazy[node]
if start != end:
lazy[node * 2] += lazy[node]
lazy[node * 2 + 1] += lazy[node]
lazy[node] = 0
def update(node, start, end, left, right):
update_lazy(node, start, end)
if right < start or end < left:
return
if left <= start and end <= right:
tree[node] += end - start + 1 # 인기도는 1씩 올라가므로 구간 길이만큼 더하면 된다.
if start != end:
lazy[node * 2] += 1
lazy[node * 2 + 1] += 1
return
mid = (start + end) // 2
update(node * 2, start, mid, left, right)
update(node * 2 + 1, mid + 1, end, left, right)
tree[node] = tree[node * 2] + tree[node * 2 + 1]
def query(node, start, end, left, right):
update_lazy(node, start, end)
if right < start or end < left:
return 0
if left <= start and end <= right:
return tree[node]
mid = (start + end) // 2
return query(node * 2, start, mid, left, right) + query(node * 2 + 1, mid + 1, end, left, right)
size = 24 * 60 * 60 # 하루의 전체 초는 86,400초
tree = [0] * (1 << (ceil(log2(size)) + 1)) # 트리와 lazy를 크기에 맞게 만든다.
lazy = [0] * (1 << (ceil(log2(size)) + 1))
total = 0 # 모든 인기도의 합
for _ in range(int(input())): # 각 사람이 티비를 시청한 구간을 입력받는다.
left, right = map(lambda x: time(x), input().split(' - ')) # 구간을 초 단위로 바꿔서 저장
# 만약 right가 left보다 낮으면
# 0 - right 구간과 left - 86,399 구간을 업데이트하면 된다.
# 그리고 인기도의 합에 구간의 길이만큼 더하자.
# 0 - right 구간과 left - 86,399 구간은
# right + 1 - left - 1의 구간의 길이를 전체 초에서 빼면 길이가 나온다.
if right < left:
update(1, 0, size - 1, 0, right) # 0 - right
update(1, 0, size - 1, left, size - 1) # left - 86,399
total += size - left + right + 1
else: # 아니면 left - right 구간을 업데이트하면 된다.
update(1, 0, size - 1, left, right)
total += right - left + 1
for _ in range(int(input())): # 인기도를 구하려는 구간을 입력받는다.
left, right = map(lambda x: time(x), input().split(' - ')) # 구간을 초 단위로 바꿔서 저장
# 만약 right가 left보다 낮으면
# 0 - right 구간과 left - 86,399 구간을 구해야 하니깐
# right + 1 - left - 1 구간을 더해 전체 인기도에서 빼면 된다.
# 그리고 구간의 길이만큼 나눠서 출력
if right < left:
popularity_sum = total - query(1, 0, size - 1, right + 1, left - 1)
print(format(popularity_sum / (size - left + right + 1), '.10f'))
else: # 아니면 left - right 구간의 합을 구하고 구간의 길이만큼 나눠서 출력
popularity_sum = query(1, 0, size - 1, left, right)
print(format(popularity_sum / (right - left + 1), '.10f'))여담
lazyprop 문제들은 조금만 난이도가 올라가면 발상이 중요해지는 것 같다.
푸는 방법 자체는 비슷하지만, 그걸 어떻게 세그먼트 트리로 적용을 해서 풀어내느냐를 생각하는 것이 너무 어렵다.
