[우선순위큐]백준 13334번 철로 with Python3 ★

https://www.acmicpc.net/problem/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에 넣어준다
        roads.append(road)
roads.sort(key=lambda x:x[1]) #그리고 큰원소[1]를 기준으로 sort

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) 
#힙의 최소값이 철로의 끝점 road[1]-d에 있는지 확인하고 없으면 pop!
            if not heap: 
                break
        heapq.heappush(heap, road)

    answer = max(answer, len(heap)) 
#이렇게 answer에 최대 값만 넣어준다.

print(answer)

출처:https://velog.io/@piopiop/%EB%B0%B1%EC%A4%80-13334-%EC%B2%A0%EB%A1%9C%ED%8C%8C%EC%9D%B4%EC%8D%AC

 

해석

정답을 생각보다 빠르게 봐버렸다. 이번에는 적절한 조언이 없었기에 어떤 방향으로 구현을 해가야하는지 감이 안잡혔다.

 

기본적으로 우선순위 큐, 혹은 heap 관련은 어떤 식으로 써먹어야할지 쉽게 생각나지가 않는다. 간단한듯 어려운 개념인것같다.

 

코드 자체는 단순한 편이다.

정렬된 좌표들을 왼쪽에서부터 훑어 올라가며 각 경우의 오른쪽 끝점에서 왼쪽으로 d길이의 철로를 만들었을떄 포함되는 집-오피스 들을 계속해서 answer 값에 넣기 위해 이전 값과 지금 값을 max로 비교해 결국 가장 큰 값이 모든 좌표를 탐색했을때 남아있는 식이다.