[BOJ][Python] 백준 13334번: 철로

1일 1PS 57일차!

📚 문제

---

골드 2 철로

💡 풀이 과정

---

• 우선 N 개의 데이터를 정렬한다.
  • 각 지점을 입력 받을 때에도 정렬 받아 입력 받고
  • 전체 리스트도 2번째 인덱스, 1번째 인덱스를 우선순위로 정렬한다.
• 이후 끝점을 기준으로 for 문을 돌면서 해당 점을 heap 에 삽입한다.
  • 이미 정렬되어있기에 확인해할 것은 시작점뿐이므로 heap 에도 시작점만 넣어도 된다.
  • minHeap 을 사용해서 시작점들 중에서 최소값이 지금 철로 안에 존재하는 지 확인한다.
  • 이 역시 이미 정렬되어있으므로 현재 철로에서 제외시킨다면 다음 루프에서도 당연하게 제외되어야하므로 pop 을 진행한다.
• 각 시점에서 heap 의 사이즈가 최대 연결 가능 수이다.

📌포인트

---

• 정렬을 통해 많은 것이 미리 결정되어진다.

💻 코드

---

import heapq

N = int(input())
distances = [[a, b] if a < b else [b, a] for _ in range(N) for a, b in [map(int, input().split())]] # sort 해서 입력을 받는다.
D = int(input())

# dis 끝 점 기준으로 정렬 .. 같은 경우 앞 점이 작은 경우가 우선적으로..
distances.sort(key=lambda x: (x[1], x[0]))

# Min_Heap 생성
min_heap = []
max_count = 0

for dis in distances:
    heapq.heappush(min_heap, dis[0])
    end = dis[1]
    start = end - D

    # 가장 왼쪽에 있는 점부터 [end, start] 사이에 존재하는 지 확인한다. 지금 존재하지 않으면 이후에도 절대 존재하지 않으니 순서대로 확인한다.
    while min_heap and min_heap[0] < start:
        heapq.heappop(min_heap)
    max_count = max(max_count, len(min_heap))

print(max_count)