[python] 백준 13334 :: 철로 (우선순위 큐)

[철로]

# 문제
집과 사무실을 통근하는 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의 임의의 선분에 대하여, 집과 사무실 위치가 모두 그 선분에 포함되는 사람들의 최대 수를 한 줄에 출력한다. 

풀이

전체 코드

import sys
import heapq
n = int(input())

datas = []
for _ in range(n):
    a, b = list(map(int, sys.stdin.readline().split()))
    datas.append((max(a, b), min(a, b)))  # 끝점, 시작점

# 입력받은 데이터들을 '끝점'을 기준으로 오름차순 정렬
datas.sort()

d = int(input())  # 거리
heap = []  # 기차를 탈 수 있는 사람들의 '출발점'을 담을 최소힙
max_result = 0  # 결과를 담을 변수

for item in datas:
    # '끝점 - 출발점'이 d와 같거나 작으면 heap에 '출발점'을 push
    if item[0]-item[1] <= d:
        heapq.heappush(heap, item[1])
    else:
        continue

    # heap에 담긴 데이터들 중에서 지금 담은 데이터의 '끝점'과 계산해서 거리가 d를 초과하는 데이터들 전부 제거
    while heap:
        start = heap[0]  # 제일 작은 출발점
        # 지금 담은 데이터의 끝점 - 제일 작은 출발점
        if item[0] - start > d:
            heapq.heappop(heap)
        else:
            break

    max_result = max(len(heap), max_result)
print(max_result)

 

0. 풀이 방법

• 사무실과 집의 위치를 대소 비교를 통해 (끝점, 시작점)으로 데이터를 입력받고,
• 끝점을 기준으로* 오름차순으로 정렬한다.
• 각 끝점 - 시작점이 철로의 길이와 같거나 작은 데이터들만 남긴다.
• 남은 데이터들을 하나씩 돌면서 시작점을 heap에 담고,
  돌고 있는 데이터의 끝점을 기준으로 범위 안에 드는 시작점들의 개수를 센다.

 

1. 사무실과 집의 위치를 입력받는다.

• 사무실과 집의 방향은 따질 필요가 없다.
• 단순히 큰 값과 작은 값만 비교해서 큰 값이 앞으로 오는 튜플을 만들어서 datas 리스트에 담는다.

datas = []
for _ in range(n):
    a, b = list(map(int, sys.stdin.readline().split()))
    datas.append((max(a, b), min(a, b)))  # 끝점, 시작점

• 큰 값이 앞으로 오게 한 이유는, 끝점을 기준으로 오름차순 정렬을 하기 위함이다!

# 입력받은 데이터들을 '끝점'을 기준으로 오름차순 정렬
datas.sort()

 

2. 범위 안에 드는 출발점들을 힙에 담는다.

• 끝점에서 출발점을 뺐을 때 (= 거리가), d와 같거나 작으면 출발점을 힙에 담는다.
• d보다 크면 따질 필요가 없으니 다음 반복으로 넘어간다. (continue)

for item in datas:
    # '끝점 - 출발점'이 d와 같거나 작으면 heap에 '출발점'을 push
    if item[0]-item[1] <= d:
        heapq.heappush(heap, item[1])
    else:
        continue

 

3. 범위에 드는 데이터의 개수를 센다.

• 현재 철로의 범위는, 끝점 중에서 제일 큰 값에서 d를 뺀 값까지이다.
• 이 범위에 들지 못하는 출발점을 가진 경로들은 지금의 철로의 범위에 들지 못하므로 제외해야 한다.
• 지금까지의 끝점들 중에서 제일 큰 값은, 지금 반복문에서 돌고 있는 item의 끝점이다.
  (지금 반복문을 돌고 있는 datas 리스트가 끝점을 기준으로 오름차순 정렬되어 있기 때문!)
• 즉, 지금 item의 끝점에서 start를 뺐을 때 d와 같거나 작은 데이터들만 철로의 범위에 든다.
• 범위에 들지 않는 item들은 전부 앞으로도 범위에 들 수 없으니 heap에서 제거해버린다.
  (리스트가 끝점을 기준으로 오름차순 정렬되어 있어서
  끝점은 현재 데이터보다 작거나 같을 수밖에 없으니 출발점만 확인하면 된다.)

    # heap에 담긴 데이터들 중에서 지금 담은 데이터의 '끝점'과 계산해서 거리가 d를 초과하는 데이터들 전부 제거
    while heap:
        start = heap[0]  # 제일 작은 출발점
        # 지금 담은 데이터의 끝점 - 제일 작은 출발점
        if item[0] - start > d:
            heapq.heappop(heap)
        else:
            break