소스코드
힙 자료구조 사용
import sys
import heapq
n = int(input().strip())
peoples = []
for _ in range(n):
h, o = map(int, input().strip().split())
peoples.append((min(h,o), max(h,o)))) # (시작지점, 끝지점) 형태
peoples.sort(key=lambda x: x[1])
d = int(input().strip()) # 철로 선분 길이
result = 0 # 철로 선분에 모두 포함되는 사람들의 최대 수
min_heap = []
for start_point, end_point in peoples:
# 철로 길이보다 두 좌표의 거리가 길면 패스
if (end_point - start_point) > d:
continue
heapq.heappush(min_heap, start_point)
while min_heap and min_heap[0] < end_point - d:
heapq.heappop(min_heap)
result = max(result, len(min_heap))
print(result)
Python
복사
풀이
•
우선 떠올렸던 것은 이중반복문을 사용하면 안된다는 점이었습니다.
◦
최대 O(NlogN)에서 마무리지어야 시간초과가 발생하지 않을 것이라고 판단했습니다.
•
입력값에 대해서는, 각 라인의 최대/최소를 찾아 튜플 형태로 (시작 좌표, 끝 좌표)를 사용했습니다.
◦
전체 입력을 받고 나서는 끝 좌표를 기준으로 오름차순 정렬을 했습니다. 이유는 시작 좌표를 기준으로 오름차순 정렬을 시도하면 끝이 언제인지는 다시 파악을 해야하기 때문에 우선 끝 좌표로 오름차순 정렬을 하자고 생각했습니다.
•
최소힙을 택한 이유는, 저는 end_point를 우측 끝으로 두고 d를 왼쪽으로 보내는 느낌으로 사용했는데, 이때 최소힙에 있는 가장 왼쪽의 시작점이 end_point - d보다 왼쪽에 있다면 철로에 포함이 안되므로 매 경우 작은 값이 곧바로 나올 수 있도록 최소힙을 사용했습니다.
복기
•
최소힙을 사용해야하는 이유에 대해 명확히 설명해내지 못했습니다(시간복잡도나 사용 이유 등)
◦
본능적으로 사용한 느낌?
•
N이 최대 10만 개인데, 순회할 생각을 안하고 다른 방식이 있나 생각해서 시간 낭비를 했습니다.
•
정렬을 끝점을 기준으로 사용해 끝점에서 왼쪽으로 d만큼 거리를 설정한다는, 입력값들의 점을 이용해 d만큼 범위를 설정한다는 아이디어를 떠올리지 못했습니다.
◦
잊혀질 때쯤 다시 풀어봐야겠습니다.