[백준 13334] 철로(파이썬)

백준 13334 - 철로

import sys
import heapq

n = int(sys.stdin.readline())
road_info = []
for _ in range(n):
    road = list(map(int, sys.stdin.readline().split()))
    road_info.append(road)

d = int(sys.stdin.readline())
roads = []
for road in road_info:
    house, office = road
    if abs(house - office) <= d:
        road = sorted(road)
        roads.append(road)
roads.sort(key=lambda x:x[1])

answer = 0
heap = []
for road in roads:
    if not heap:
        heapq.heappush(heap, road)
    else:
        while heap[0][0] < road[1] - d:
            heapq.heappop(heap)
            if not heap:
                break
        heapq.heappush(heap, road)
    answer = max(answer, len(heap))

print(answer)

'우선순위 큐(힙)' 문제들은 어떻게 사용할지를 떠올리는 게 쉽지 않은 것 같다.

풀이

이번 문제는 각 경로를 순회하면서 집, 사무실 중 좌표값이 큰(더 오른쪽에 있는) 점에서 왼쪽으로 d 길이의 철로를 깔았을 때 철로에 몇개의 경로가 포함되는지를 확인하는 방식으로 문제를 풀 수 있다.

1) 먼저 각 사무실, 집 정보를 roads에 저장할 때 사무실과 집의 거리가 d보다 크다면 d를 어떻게 움직여도 포함될 수 없으므로 저장하지 않는다. d보다 작거나 같다면 좌표정보를 오름차순으로 정렬해 저장해준다.

2) 철로의 시작점을 가장 작은 것부터 시작할 수 있도록 raods를 본인의 원소 중 큰 원소를 기준으로 오름차순 정렬해준다. (앞서 말한 것처럼 더 멀리있는 좌표값에서 왼쪽으로 철로를 깔 것이기 때문에 더 멀리있는 좌표값 (= 큰원소)가 시작점이 된다)
roads.sort(key=lambda x:x[1])

3) 철로의 시작점을 가장 작은 것부터 순회하면서 차례대로 힙에 넣어주게 된다. 이때 힙에 존재하는 가장 작은 값이 철로의 끝점안에 있는지 확인해 철로 내에 있지 않다면 힙에서 제거한다.
while heap[0][0] < road[1] - d:
heapq.heappop(heap)

아래와 같이 roads = [[1, 5], [3, 5], [2, 7]], d = 5이고 heap =[[1, 5], [3, 5]]인 상황을 가정해보자.
그 다음 원소인 [2, 7]에서 큰 좌표값인 7에서 왼쪽으로 철로를 그어보면 7에서 2까지 그을 수 있다. 이때 heap[0] = [1, 5]는 시작점이 2보다 왼쪽에 있으므로 heap에서 빼주고 다음 heap[0] = [3, 5]는 2 ~ 7 범위 내에 있으므로 while문을 종료한다.

이 같은 방식으로 roads의 모든 원소를 순회하고 heap의 길이의 최대일 때의 값을 반환해주면 된다.

철로의 시작점을 각 원소의 작은 좌표값으로 잡고 오른쪽으로 뻗는 방식으로 풀다가 많은 어려움을 겪었다.
아직 많이 부족하다는 것을 다시 한 번 깨닫게 된 문제였다.

피드백 환영합니다.
-끝-