[백준 2024/09/12] 13334번 철로

1. 문제

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

 

2. 접근 방법

 

처음에 문제를 풀 때, 헤맸던 요인이 무엇일까... 고민해 보았는데 heap에 처음부터 모든 값을 넣고 최솟값을 출력해야한다는 고정 관념에서 기인한 것 같다. heap을 약간의 저장소로 바라보았으면 더 좋지 않았을까 생각한다.

 

또한 처음에, 좌표 상에서 ( x, y ) ...( x < y )로 선분을 저장한다고 가정했을 때,  x를 기준으로 시작 점을 잡아 + L을 한 것에서 더 어려움을 겪었다.

y를 기준으로 시작 점을 잡아 -L을 해서 해당 범위 안에 x가 있다면 ... 이라는 다른 경우도 한번 생각해 보아야 하는데 지쳤다.......

 

우선 문제 풀이로 넘어가자.

좌표 값들 x y로 받아서, min_heap이라는 heap에다가 추가해 주었다.

이를 ( y, x )순으로 min_heap에 저장하여 y를 기준으로 오름차순 정렬을 이용할 수 있도록 하였다.

while 문에서 min_heap이 빌 때까지 pop을 해주었다.

y - l (주어진 철도 길이) 를 이용해서, 어떤 좌표 상까지 선분이 포함될 수 있을 지 좌표로 판단하였다.

 

그 y - l 위로 좌표가 있다면 선분이 포함 되는 것이기 때문에, 이를 save_heap 이라는 heapq에다가 저장해 주었다.

 

그 다음 y 값을 받아 ( y - l ) 위로 x가 포함된다면 똑같이 save_heap 에다가 넣어주면 된다.

또한, 새로 리뉴얼 된 기준에 save_heap에 포함되는지 유무를 포함되는 save_heap[0]으로 파악해 준다.

그래서 포함될 때까지, pop을 진행해주면 된다.

 

len(save_heap) 으로 포함된 선분의 길이를 계산해 주면 된다.

그 중 max 값을 출력하면 된다.

 

3. 코드

import heapq

max_count = 0
min_heap = []
save_heap = []
n = int(input())

for i in range(n):
    x, y = map(int, input().split())
    if x > y:
        x, y = y, x
    heapq.heappush(min_heap, (y, x))

l = int(input())
while min_heap:
    y, x = heapq.heappop(min_heap)
    l_s = y - l

    while save_heap and save_heap[0] < l_s:
        heapq.heappop(save_heap)

    if l_s <= x:
        heapq.heappush(save_heap, x)

    if max_count < len(save_heap):
        max_count = len(save_heap)

print(max_count)