[복기] 13334번: 철로

아래 글을 철로 풀이 글을 보고 정리하였습니다.

문제

백준 13334번: 철로

알고리즘 분류

• 자료구조
• 정렬
• 스위핑
• 우선순위 큐

나의 풀이: 단순 스위핑

우선순위큐를 어떻게 써야할지 몰라서, 그냥 단순 라인 스위핑만 적용했다. 탐색 범위를 좁혀서 시간초과를 벗어나긴 했으나, 2%에서 그냥 틀렸다.

로직은 간단하다. 정렬 후 철로의 왼쪽 좌표를 lIdx를 사람의 제일 왼쪽 값을 주고 증가시키면서 사람이 몇명이나 포함되는지 계산했다.

전체 코드

import sys
input = sys.stdin.readline

n = int(input())
trains = [[0, 0] for _ in range(n)]
for i in range(n):
    l, r = map(int, input().split())
    if l > r:
        trains[i] = [r, l]
    else:
        trains[i] = [l, r]
d = int(input())

trains.sort(key=lambda x: x[0])

answer = 0
lIdx = 0
while lIdx < n:
    left = trains[lIdx][0]
    right = left + d
    count = 0
    for train in trains[lIdx:n]:
        if left <= train[0] and train[1] <= right:
            count += 1
            continue
        if train[0] >= right:
            break
    
    while lIdx < n:
        if trains[lIdx][0] != left:
            break
        lIdx += 1
    
    answer = max(answer, count)

print(answer)

솔루션: 우선순위 큐 + 스위핑

철로 우선순위큐 풀이1
철로 우선순위큐 풀이2

"우선순위큐를 이런 식으로 쓸 수 있구나"를 알게되었다. 우선, n개의 선분들을 오른쪽 끝점을 기준으로 오름차순 정렬을 한다. 그리고 각 i번째 선분의 오른쪽 끝점을 철로의 오른쪽 끝점으로 잡고, 오른쪽 끝에서부터 왼쪽으로 길이 d 이내에 있는 선분의 최대 개수를 계산한다.

train.sort(key=lambda x: x[1]) ## 오른쪽 끝점 기준 정렬

answer = 0
heap = []
for s, e in train:
    lim = e - d
    if s >= lim: # 현재 선분이 철로에 포함되면, push
        heappush(heap, s)
    while heap and heap[0] < lim: # 힙에 저장된 이전 선분들의 시작점이 철로를 벗어나면, pop
        heappop(heap)
    answer = max(answer, len(heap)) # i번째 철로에서의 최대 개수 계산

heap은 현재 철로에 포함된 선분의 왼쪽 끝점을 저장한다. 선분의 왼쪽 끝점이 철로의 범위에서 벗어나면, heappop(heap)으로 뺀다. 이를 통해 heap에는 항상 철로 범위 내의 선분만을 저장할 수 있게된다. heapq를 사용했기에 O(N * log N)의 시간복잡도를 가진다.

전체 코드

import sys
input = sys.stdin.readline
from heapq import heappush, heappop

n = int(input())
train = [[0, 0] for _ in range(n)]
for i in range(n):
    l, r = map(int, input().split())
    if l > r:
        train[i] = [r, l]
    else:
        train[i] = [l, r]
d = int(input())

train.sort(key=lambda x: x[1])

answer = 0
heap = []
for s, e in train:
    lim = e - d
    if s >= lim:
        heappush(heap, s)
    while heap and heap[0] < lim:
        heappop(heap)
    answer = max(answer, len(heap))
print(answer)