🖥 문제
📝 답안
오른쪽으로 철로를 옮겨가면서 해당 철로에 포함되는 선분의 개수를 세면 될 것이다.
그렇다면 철로는 어떻게 옮기는 것이 좋을까?
가장 쉬운 방법을 생각해보면 철로를 한 칸씩 옮겨가면서 해당 철로에 포함되는 사람의 수를 세는 것이다.
그런데 좌표의 범위는 −100,000,000이상, 100,000,000 이하의 매우 큰 범위이므로, 위와 같은 방법으로 문제를 풀려고 한다면 시간 초과가 날 것이다.
따라서 좌표가 아닌 각각의 사람을 기준으로 철로를 옮겨가며 답을 찾아야 한다.
현재 철로에 포함되는 사람들의 배열을 두고, 철로를 옮길 때마다 새로 포함되는 사람을 배열에 추가하고, 벗어나는 사람은 배열에서 제거하는 방식을 사용하면 된다.
파이썬의 heapq 모듈을 사용하면 이를 간편하게 구현할 수 있을 것이다.
그런데 여기에서 고민이 되는 지점이 또 하나가 있다. 각 사람의 시작 지점을 기준으로 철로를 만들어야 할까? 아니면 끝 지점을 기준으로 철로를 만들어야 할까?
나는 처음에 시작 지점을 기준으로 철로를 만드는 것을 생각했었다. 하지만 이렇게 하는 경우 까다로웠던 점은 철로를 옮길 때마다 시작 지점을 벗어난 사람이 없는지, 끝 지점에 새로 들어온 사람이 있는지 등 고려해야 할 사항이 많았던 것이다.
반면, 끝 지점을 기준으로 철로를 만들 때는 고려해야 할 사항이 훨씬 간단했다.
왜냐하면 끝 지점을 기준으로 하면, 힙에 이미 들어와 있는 사람들은 현재 철로보다 끝 좌표가 작은 사람들이기 때문에 시작 지점만 고려하면 됐기 때문이다. 즉, 철로의 시작 지점보다 시작 좌표가 작은 사람들이 있으면 힙에서 제거해주면 되는 것이다.
따라서 아래와 같이 답안을 작성할 수 있다.
import sys
import heapq
# 입력값 받기
n = int(sys.stdin.readline().strip())
locations = [] # ([(시작 좌표, 끝 좌표) ...]
for _ in range(n):
h, o = map(int, sys.stdin.readline().strip().split())
# 집과 사무실 중 좌표값이 낮은 것을 앞에, 좌표값이 높은 것을 뒤에 넣어줌
locations.append((min(h, o), max(h, o)))
d = int(sys.stdin.readline().strip())
# 선분의 끝점을 기준으로 오름차순 정렬한 다음, 앞점을 기준으로 오름차순 정렬
locations.sort(key=lambda x: (x[1], x[0]))
heap = []
max_cnt = 0
for location in locations: # 각 사람의 좌표를 기준으로 반복문 돌기
start, end = location
heapq.heappush(heap, start) # 최소 힙. pop했을 때 start가 작은 것부터 나올 수 있도록
line_start = end - d # 현재 사람의 끝 좌표를 기준으로 철로의 시작 지점 계산
while heap and heap[0] < line_start: # heap[0] = 힙에 저장된 시작 지점 중 최소값
heapq.heappop(heap) # 철로의 시작 지점보다 시작 좌표가 작은 경우 철로를 벗어나므로 pop
max_cnt = max(max_cnt, len(heap)) # 현재 철로에 포함되는 사람 수가 최대값인 경우 갱신
print(max_cnt)