문제 링크: https://www.acmicpc.net/problem/13334

Thumbnail: Photo by Irina Iriser (Unsplash)

우선순위 큐를 활용해 스위핑을 진행하는 문제입니다. 정렬 순서로 인해서 많은 고민을 했던 것 같습니다.

풀이

아이디어

먼저, 스위핑을 위해 입력을 정렬해줘야 합니다. 스위핑(sweeping) 알고리즘이란, 넓은 범위로 주어지는 입력을 정렬한 뒤 순차적으로 읽어가는 기법입니다.

입력 전처리

입력 받은 집 좌표($h_i$)와 사무실 좌표($o_i$)에 대해, $h_i \leq o_i$는 보장되지 않습니다. 계산의 편의를 위해, $h_i \leq o_i$가 되도록 좌표를 정리해줘야 합니다.

이후 풀이에서, 편의상 작은 쪽 좌표를 $h$, 큰 쪽 좌표를 $o$라고 부르겠습니다.

이후, 입력으로 주어진 좌표들 중 집과 사무실의 좌표 차가 선분의 길이인 $D$ 이상인 좌표들은 배열에서 제외하고, 나머지 좌표들을 o를 기준으로 정렬합니다.

스위핑

이제, 정렬된 입력 좌표들에 대해 다음을 반복합니다:

1. 현재 처리중인 좌표 $(s, e)$에 대해, 끝점 $e$를 기준으로 선분을 정의합니다.
   이때, 선분의 시작점은 $e - D$가 됩니다.
2. 우선순위 큐(힙)에 현재 좌표의 시작점인 $s$를 추가합니다.
3. 우선순위 큐가 비지 않은 상태이고, 우선순위 큐에서 현재 선분에 포함되지 않는 모든 값을 제거합니다.
   모든 좌표를 $o$를 기준으로 정렬했기 때문에, 현재 우선순위 큐에 저장된 모든 시작점은 $e$보다 작거나 같습니다. 따라서, 시작점만 가지고도 선분에 포함되는지 여부를 확인할 수 있습니다.
4. 선분에 포함되지 않는 모든 좌표를 우선순위 큐에서 제거한 뒤, 우선순위 큐에 남아있는 좌표의 수를 기존 최댓값과 비교해 최댓값을 갱신합니다.

전체 코드

from heapq import heappush, heappop
input = open(0).readline

N = int(input())
# 1. 모든 좌표를 읽으면서 (작은 값, 큰 값) 형태로 정규화하여 저장
all_people = [tuple(sorted(map(int, input().split()))) for _ in range(N)]

D = int(input())

# 2. 좌표 차가 D보다 큰 경우를 제외하고, 모든 좌표를 끝점을 기준으로 정렬
valid_people = sorted(filter(lambda p: p[1] - p[0] <= D, all_people), key=lambda x: x[1])

# 우선순위 큐를 활용해 스위핑
contained_heap = []
max_people = 0

for start, end in valid_people:
    rail_start = end - D # 언제나 끝점을 기준으로 선분을 계산한다.
    
    heappush(contained_heap, start)
    
    # heapq로 정렬된 우선순위 큐의 0번에는 항상 최솟값이 위치한다.
    while contained_heap and contained_heap[0] < rail_start:
        heappop(contained_heap)
    
    max_people = max(max_people, len(contained_heap))

print(max_people)

시행착오

처음에는 선분이 아닌 좌표를 기준으로 생각했었습니다. 좌표들을 $h$를 기준으로 정렬하고, 한 좌표의 $h$로부터 길이 $D$만큼 선분을 잡은 뒤 다음 좌표가 선분을 벗어난다면 그 좌표로 선분을 이동시키는 방법을 생각했는데, 정작 다음과 같은 케이스에서 최댓값을 제대로 찾지 못하는 점을 발견했습니다.

# input
4
1 4
1 4
2 5
3 4
3
# output
3

이런 케이스를 온전히 처리하기 위해, 정렬을 $h$가 아닌 $o$를 기준으로 진행하게 되었습니다.