백준 13334번: 철로

백준 13334번: 철로

import heapq
n=int(input())
nums = []
for _ in range(n):
    h,o = map(int,input().split())
    nums.append((min(h,o),max(h,o)))
d=int(input())
candidate_num = []
for i in range(n):
    if nums[i][1] - nums[i][0] <=d:
        candidate_num.append(nums[i])

candidate_num.sort(key=lambda x:x[1])
ans = 0
q = []

for i in candidate_num:
    if not q:
        heapq.heappush(q,i)
    else:
        while q[0][0]<i[1] - d:
            heapq.heappop(q)
            if not q:
                break
        heapq.heappush(q,i)
    ans = max(ans, len(q))
print(ans)

블로그를 옮기려고 하고 있긴한데, 아직 정리가 안 돼서 일단 지금은 여기로 올린다.
일단 데이터 범위를 확인했을 때 브루트포스는 아닌 건 확실했고, 그래서 처음에는 이분탐색으로 접근했다.(l_min, r_max를 구해서 r_max-l_min<d 일때까지 값을 찾는 방식) 하지만 이렇게 접근하면 중간에 걸치는 경우 등 때문에 제대로 값을 찾지 못하는 것 같다. 그래서 찾아보니 우선순위 큐로 접근하는 게 맞는 문제였다.
우선순위 큐는 완전이진트리 형태로, 중복값이 허용되며 부모노드 - 서브트리간 대소 관계가 성립된다.
위와 같이 하면 각 후보 length의 h를 기준으로 만든 L에 포함되는 선분의 개수가 len(q)가 된다.
그렇다면 이건 그냥 deque같은 걸로 구현해도 될 것 같기도 한데, 왜 우선순위 큐로 구현해야할까?
q를 탐색하는 과정에서, 시작점이 가장 작은 경우부터 확인해야하기 때문에(그냥 큐를 사용하면 push하는 과정에서 순서가 꼬일 것임) 이를 이용해서 구현하는 것이다.
우선순위 큐를 활용해서 문제를 풀어본 적이 별로 없어서 바로 생각이 안 났던 것 같다. 비슷한 문제들을 좀 더 풀어봐야겠다.