[골드 2] 백준 13334 - 철로 (파이썬)

https://www.acmicpc.net/problem/13334

풀이

• N개의 사람 정보 (집과 사물실의 좌표)
• 철로의 길이는 D로 고정됨
• 하나의 철로로 최대 몇 명을 커버할 수 있는가?
• 즉 철로구간[a, a + D] 내에 (start, end) 모두 포함된 사람이 최대 몇명인지?

일단 코드를 잘못 짠 부분이 있다.

for i in range(N) :
    pq.put(X[i][1])

• 그냥 끝점 기준으로 넣고, 무조건 X[i][1] + D를 오른쪽 끝이라 생각해버렸다.
• 시작점이 X[i][0] 보다 작은 사람도 같이 포함될 수 있다.

이 뿐만 아니라 시작점보다 왼쪽인 선분을 제외하기 않았다.

• 철로 구간 [x, x + D] 안에 들어오려면, start ≥ x and end ≤ x + D 여야한다.
• 따라서 end를 기준으로 정렬하고, 우선순위 큐에 시작점을 넣고, 범위 밖인 start는 제거야해 한다.

근데 이게 왜 통과하는거지,,,,

로직 설명

1. (start, end)를 정렬해 정규화
2. 철로는 항상 사람의 end 지점에 오른쪽 끝이 닿도록 설치한다고 가정
3. → 이게 가능한 모든 사람을 커버할 수 있는 방식
4. 현재 사람의 end에서 왼쪽으로 D만큼 뺀 지점보다 start가 작은 사람들은 제거
5. start를 우선순위 큐에 넣고 큐의 크기로 최댓값 갱신

시간 복잡도 분석

• 정렬: O(N log N)
• 우선순위 큐 연산: O(N log N)
• 전체: O(N log N)

코드

# 백준 13334 - 철로
# 분류 : 우선순위 큐

from queue import PriorityQueue

N = int(input())
R = [list(map(int, input().split())) for _ in range(N)]
D = int(input())

X = []
for i in range(N) :
    if R[i][0] > R[i][1] : 
        R[i][0], R[i][1] = R[i][1], R[i][0]
    
    if R[i][1] - R[i][0] > D :
        continue

    X.append(R[i])

N = len(X)
X.sort()
pq = PriorityQueue()
for i in range(N) :
    pq.put(X[i][1])

answer = 0
for i in range(N) :
    # X[i][0] ~ X[i][0] + D
    while pq.qsize() != 0 :
        x = pq.get()
        if x > X[i][0] + D :
            pq.put(x)
            break

    answer = max(answer, N - i - pq.qsize())

print(answer)