[백준 파이썬 13334번 철로] heapq의 활용

문제 핵심

1. 시작점에서 고려하지 말고, 끝 점에서 고려하자!

시작점에서 고려할 경우 새로운 노선이 들어왔을 때 두 가지를 확인해야한다

1. 새로운 노선의 시작이 범위를 벗어나는가?
2. 새로운 노선의 끝이 범위를 벗어나는가?

하지만 새로운 노선의 끝을 기준으로 범위를 설정하면 범위의 시작부분만 확인하면 된다.

 

2. 왜 정렬을 했는데 우선순위 큐를 써야하는 문제인 것일까?

정렬의 기준이 끝을 기준으로 했기 때문이다.

범위를 벗어나는 노선을 제거할 때는 종료지점 기준이 아닌 시작지점 기준으로 작은 수부터 제거해야한다.

그러니 값이 들어올 때만 정렬을 해주는 것은 엄청난 시간 복잡도가 필요하다.

따라서 이를 힙으로 해결한다.

-> 힙을 사용하는 이유 : 값이 들어올 때마다 정렬이 필요한 경우 or 두 가지 기준의 정렬이 동시에 필요한 경우

 

from heapq import heappush, heappop

N = int(input())
house_ls = []
for _ in range(N):
    h, o = map(int, input().split())
    house_ls.append([min(h, o), max(h, o)])
D = int(input())

roads = []
for road in house_ls:
    house, office = road
    if abs(house - office) <= D:
        roads.append(road)

roads.sort(key=lambda x: x[1])

wait = []
MAX = len(wait)
for road in roads:
    heappush(wait, road[0])
    while wait and wait[0] < road[1] - D:
        heappop(wait)
    MAX = max(MAX, len(wait))

print(MAX)

https://www.acmicpc.net/problem/13334