문제
- 백준 URL: 철로
- 난이도 골드 2
풀이
import sys
import heapq
input = sys.stdin.readline
n = int(input())
l = []
for _ in range(n):
h,o = map(int,input().split())
s,e = min(h,o), max(h,o)
l.append((s,e))
d = int(input())
valid_l = []
for s,e in l:
if e-s <= d:
valid_l.append((s,e))
valid_l.sort(key=lambda x: (x[1],x[0]))
max_cnt = 0
pq = []
for s,e in valid_l:
rail_start = e - d
heapq.heappush(pq, s)
while pq and pq[0] < rail_start:
popped = heapq.heappop(pq)
current_count = len(pq)
if current_count > max_cnt:
max_cnt = current_count
print(max_cnt)
스위핑과 우선순위 큐(heapq)를 이용해 해결할 수 있는 문제이다.
우선, 입력 값을 받은 후 철로 길이보다 집-사무실 거리가 먼 경우는 제외한다. 그리고 끝 점을 기준으로 오름차순 정렬한다. 만약 끝점이 같다면, 시작점을 기준으로 오름차순 정렬한다.
이제 현재 철로에 포함될 수 있는 후보들의 시작점을 최소 힙(Min-Heap), 즉 우선순위 큐에 저장한다. 철로의 시작 지점(현재 끝점 - d)보다 왼쪽에 있는, 즉 더 이상 철로에 포함될 수 없는 사람들을 가장 빠르게 찾아내서 제거하기 위함이다.
알고리즘은 이렇다.
a. 정렬된 리스트에서 사람 i의 (start_i, end_i)를 가져온다.
b. 이 사람을 포함시키려면, 철로의 오른쪽 끝이 최소한 end_i에 있어야한다. 그럼 철로의 왼쪽 시작은 end_i - d가 된다.
c. 이 사람 i는 당연히 이 철로에 포함될 수 있으니, start_i를 우선순위 큐에 push한다.
d. 이제 우선순위 큐를 보면 큐 안에 있는 시작점들 중에 end_i - d보다 작은 게 있다면? 그건 이제 현재 철로의 범위를 벗어났다는 뜻이므로 pop 한다.
e. 이 과정을 거치고 난 뒤 우선순위 큐에 남아있는 원소의 개수가, 바로 철로의 끝을 end_i에 맞췄을 때 포함되는 최대 사람 수가 된다.
f. 이 값을 계속 최댓값과 비교해서 업데이트하면, 모든 사람을 다 훑었을 때 최종적인 정답이 나오게 된다.
