집과 사무실을 통근하는 n명의 사람들이 있다. 각 사람의 집과 사무실은 수평선 상에 있는 서로 다른 점에 위치하고 있다. 임의의 두 사람 A, B에 대하여, A의 집 혹은 사무실의 위치가 B의 집 혹은 사무실의 위치와 같을 수 있다. 통근을 하는 사람들의 편의를 위하여 일직선 상의 어떤 두 점을 잇는 철로를 건설하여, 기차를 운행하려고 한다. 제한된 예산 때문에, 철로의 길이는 d로 정해져 있다. 집과 사무실의 위치 모두 철로 선분에 포함되는 사람들의 수가 최대가 되도록, 철로 선분을 정하고자 한다.
양의 정수 d와 n 개의 정수쌍, (hi, oi), 1 ≤ i ≤ n,이 주어져 있다. 여기서 hi와 oi는 사람 i의 집과 사무실의 위치이다. 길이 d의 모든 선분 L에 대하여, 집과 사무실의 위치가 모두 L에 포함되는 사람들의 최대 수를 구하는 프로그램을 작성하시오.
그림 1 에 있는 예를 고려해보자. 여기서 n = 8, (h1, o1) = (5, 40), (h2, o2) = (35, 25), (h3, o3) = (10, 20), (h4, o4) = (10, 25), (h5, o5) = (30, 50), (h6, o6) = (50, 60), (h7, o7) = (30, 25), (h8, o8) = (80, 100)이고, d = 30이다. 이 예에서, 위치 10 과 40 사이의 빨간색 선분 L이, 가장 많은 사람들에 대하여 집과 사무실 위치 모두 포함되는 선분 중 하나이다. 따라서 답은 4 이다.
입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,000이하의 서로 다른 정수이다. 마지막 줄에, 철로의 길이를 나타내는 정수 d (1 ≤ d ≤ 200,000,000)가 주어진다.
출력
출력은 표준출력을 사용한다. 길이 d의 임의의 선분에 대하여, 집과 사무실 위치가 모두 그 선분에 포함되는 사람들의 최대 수를 한 줄에 출력한다.
리스트를 정렬하고, 리스트를 단 한 번 순회하며 최댓값을 찾는다는 핵심은 비슷하다. 차이점은 우리가 구하고자 하는 최대가 '일정 길이 안에 포함되는 선분 개수의 최댓값'이라는 점이다.
선분의 길이를 잴 때, 시작점 < 끝점인 상황을 가정하면 그 길이는 (끝점 - 시작점)이다. 이 문제를 풀기 위해 조건에 해당하는 선분을 리스트에 집어넣는다고 가정하자. 리스트를 하나의 큰 선으로 생각한다면, 리스트의 실질적인 길이는 (끝점의 최댓값 - 시작점의 최솟값)이 될 것이다. 이 말인 즉슨, 리스트에 선분을 넣을 때마다 변동할 수 있는 시작점의 최솟값, 혹은 끝점의 최댓값을 우리가 기억하고 있어야 한다는 의미이다. 이럴 때 사용할 수 있는 자료구조로 우선순위 큐가 있다. 우선순위 큐의 삽입과 삭제는 O(logN)이 소요되므로 충분한 시간복잡도 내에 항상 우리가 원하는 값을 제거할 수 있다.
선분 리스트를 (끝점, 시작점)기준으로 오름차순 정렬한다.
선분을 순회하며, 다음과 같은 과정을 거친한다.
우선순위 큐에 선분을 삽입한다. 여기서 우선순위는 (시작점, 끝점)이 되어야 한다.
우선순위 큐의 '선분 길이', 그러니까 (끝점의 최댓값 - 시작점의 최솟값)은 항상 d 이하여야 한다. 앞선 정렬에 의해 앞서 삽입한 끝점은 끝점의 최댓값임이 보장된다(오름차순이므로), '선분 길이'가 d 이하가 될때까지, 우선순위 큐의 원소 삭제를 시행한다.
큐의 원소 개수(큐의 길이)를 최댓값과 비교하여 업데이트한다
순회가 끝나면 최댓값을 반환한다.
이에 따라 총 O(NlogN)의 시간복잡도 내에 풀이 가능하다!
풀이 코드
from heapq import *
import sys
input = sys.stdin.readline
def init() :
n = int(input())
line_list = list()
for _ in range(n) :
h, o = map(int, input().split())
if h > o :
h, o = o, h
line_list.append((h, o))
line_list.sort(key = lambda x : (x[1], x[0]))
d = int(input())
return line_list, d
def traversal(line_list, d) :
q = []
result = 0
for h, o in line_list :
if o - h > d :
continue
heappush(q, (h, o))
while o - q[0][0] > d :
heappop(q)
result = max(result, len(q))
print(h, o, q)
return result
def solve() :
line_list, d = init()
result = traversal(line_list, d)
print(result)
solve()
