2022.04.12 [백준] (python 파이썬) 철로

 

 

 

 

 

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

13334번: 철로

---

풀이

아래 문제는 처음 해결방법이 떠오르지 않아 구글링을 통해 여러 코드를 참고하여 해결하였다.

우선 각 정수 쌍을 오름차순 정렬하여 arr배열에 저장했다. 

이후, arr배열을 x[1]을 기준으로 오름차순 정렬했다. 이유는 철로를 확인할 때, 가장 작은 위치부터 확인하기 위해서 이다.

그리고 집, 사무실의 거리가 d보다 큰 경우는 제외하고 h_o배열에 담았다. 

이후, 철로의 시작점을 가장 작은 값부터 heap에 넣어준다. 그리고 이 때, 힙에 존재하는 가장 작은 값이 철로의 길이 안에 들어오는지 확인한다. (heap[0][0] < l[1]-d) 만약 철로의 길이 밖에 있으면 힙에 존재하는 가장 작은 값을 제거한다.

그리고 max함수를 이용해 철로의 각 위치당 최대 포함 갯수를 업데이트해준다.

import heapq
 
n=int(input())
arr=[]
for _ in range(n):
    x=list(map(int,input().split()))
    arr.append(sorted(x))
arr.sort(key=lambda x:x[1])
 
d=int(input())
h_o=[]
for l in arr:
    x,y=l
    if (y-x)<=d:
        h_o.append(l)
 
heap=[]
cnt=0
for l in h_o:
    if not heap:
        heapq.heappush(heap,l)
    else:
        while heap[0][0] < l[1]-d:
            heapq.heappop(heap)
            if not heap:
                break
        heapq.heappush(heap,l)
    cnt=max(cnt,len(heap))
 
print(cnt)