파이썬 백준 13334 철로

import sys   input = sys.stdin.readline import heapq n = int(input()) ll = [] for i in range(n) :     a, b = map(int, input().split())     ll.append([min(a, b), max(a, b)]) d = int(input()) l = [] for li in ll :     if li[1] - li[0] <= d :         l.append(li) l.sort(key = lambda x : x[1]) heap = [] maxc = 0 for x in l :     if heap == [] :         heapq.heappush(heap, x)     else :         while heap != [] and heap[0][0] < x[1] - d :             heapq.heappop(heap)         heapq.heappush(heap, x)     maxc = max(maxc, len(heap)) print(maxc)

입력받은 양 끝점이 홈인지 오피스인지는 중요하지 않으니 크기 순으로 정렬하여 리스트에 넣는다.

이중 폭이 d보다 작은 것만 골라 다시 새 리스트에 넣는다.

이를 정렬하되, 각 원소의 시작점 [0]가 아닌 끝점 [1]의 크기순으로 정렬한다.

 

시작점 [0]을 기준으로 정렬하여 철로의 시작점을 index i의 [0]에 두면, 이 철로에 몇 번째 원소까지 포함되었는지 확인하기 위해 아직 거치지 않은 i+1부터의 원소를 체크해야 한다.

어차피 철로를 두러 가야 할 미래의 원소에 체크하러 가야 하므로 계산을 두 배로 하게 된다.

반면 끝점 [1]을 기준으로 정렬하여 철로의 끝점을 i[1]에 두면, 이 철로에 어디까지 포함되었는지는 이미 거쳐간 i-1번째까지의 원소만 체크하면 된다.

이것은 거쳐간 원소를 큐에 넣는 것으로 관리할 수 있는데, 시작점이 앞인 원소부터 나가야 하니 [0]을 기준으로 정렬된 최소힙을 써야 한다.

 

즉, 머리가 [1]이고 d만큼 왼쪽으로 뻗은 철로가 다음 원소의 [1]로 이동해가며 원소를 heap에 넣는다.

매회 철로밖으로 시작점이 나온 원소를 삭제하고, heap의 길이 (=포함된 원소 수)의 max를 갱신한다.

마지막 원소의 [1]까지 철로를 배치해보고 기록된 max값을 출력한다.