[백준] 13334 : 철로 - Python

Chooooo·2024년 6월 27일

알고리즘/백준

목록 보기

196/204

문제

집과 사무실을 통근하는 n명의 사람들이 있다. 각 사람의 집과 사무실은 수평선 상에 있는 서로 다른 점에 위치하고 있다. 임의의 두 사람 A, B에 대하여, A의 집 혹은 사무실의 위치가 B의 집 혹은 사무실의 위치와 같을 수 있다. 통근을 하는 사람들의 편의를 위하여 일직선 상의 어떤 두 점을 잇는 철로를 건설하여, 기차를 운행하려고 한다. 제한된 예산 때문에, 철로의 길이는 d로 정해져 있다. 집과 사무실의 위치 모두 철로 선분에 포함되는 사람들의 수가 최대가 되도록, 철로 선분을 정하고자 한다.

양의 정수 d와 n 개의 정수쌍, (hi, oi), 1 ≤ i ≤ n,이 주어져 있다. 여기서 hi와 oi는 사람 i의 집과 사무실의 위치이다. 길이 d의 모든 선분 L에 대하여, 집과 사무실의 위치가 모두 L에 포함되는 사람들의 최대 수를 구하는 프로그램을 작성하시오.

그림 1. 8 명의 집과 사무실의 위치

그림 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 heapq
import sys
sys.stdin = open("input.txt", "rt")

# 철로. 집과 사무실 통근하는 n명의 사람들 존재
# 각 사람의 집과 사무실은 수평선 상에 있는 서로 다른 점에 위치
# 두 사람 A,B에 대해서 A의 집 혹은 사무실의 위치가 B의 집 혹은 사무실의 위치와 같을 수 있다.
# 철로의 길이 d로 정해져있음.
# 집과 사무실의 위치 모두 철로 선분에 포함되는 사람들의 수가 최대가 되도록 철로 선분 정하고자 함.
# 집과 사무실의 위치가 모두 L에 포함되는 사람들의 최대수. 시작점 끝점 모두 포함되어야 함.
# N^2 안됨

# 계속 최대인 경우를 확인하면서 진행 ?
# 시작점이 우선. 시작점 + d에 끝점이 포함이 되는지
# 안되면

n = int(input())
data = []
for _ in range(n):
    a,b = map(int, input().split())
    c = min(a,b)
    d = max(a,b)
    data.append((c,d))
d = int(input()) # 철로의 길이
cnt = 0
data.sort(key = lambda x : (x[1], x[0])) # 끝점 오름차순, 시작점 오름차순
# print(*data)
res = 0
heap = []
L = data[0][0] # 철로의 시작점 미리 설정ㄱ
# 한개씩 확인하기
for i in range(n):
    s,e = data[i] # 현재 사람의 시작시작, 끝시작
    length = e-s
    if length > d: continue # 애초에 범위 벗어나면 탈출
    heapq.heappush(heap, (s,e)) # 가능한 경우니까 일단 넣어두고
    # 불가능한 경우를 제외시키기
    if e > L+d: # 범위 초과
        while heap and heap[0][0] + d < e:
            heapq.heappop(heap)
    L = heap[0][0] # 새로 갱신 -> 갱신을 안해서 계속 틀렸었음 
    res = max(res, len(heap))

print(res)