[알고리즘] 백준 13334 철로

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

문제 유형이 우선순위큐로 알고 풀었기 때문에 어느정도 접근은 했던 것 같다. 문제 분류가 우선순위큐로 푸는것임을 몰랐다면 아마 시도하기 어려웠을 것 같다.

아래는 내가 구현한 코드이다

import heapq
import sys

N = int(sys.stdin.readline())

positions = []
for _ in range(N):
    h, o = map(int, sys.stdin.readline().split())
    # 끝점이 가까운 순으로 정렬
    heapq.heappush(positions,(max(h,o), min(h,o)))

d = int(sys.stdin.readline())

# 시작 지점 세팅
init_po, init_ph = heapq.heappop(positions)

start = min(init_ph, init_po)
end = start + d # 초기 위치에서의 철로 범위 지정

max = -sys.maxsize
count = 0
if start <= init_ph <= end and start <= init_po <= end:
    count += 1
    if max < count:
        max = count

while positions:
    ph, po = heapq.heappop(positions)
    # 철로 범위보다 끝점 위치가 벗어나 있으면, 새롭게 count, start와 end를 갱신한다.
    if end < po:
        count = 0
        start = min(ph, po)
        end = start + d

	# 두 점 모두 철로 범위 내에 들어와 있다면 count를 1증가 시킨다.
    if start <= ph <= end and start <= po <= end:
        count += 1
        if max < count:
            max = count


if max == -sys.maxsize:
    print(0)
else:
    print(max)

테스트케이스와 여러 반례를 통과했지만, 통과하지 못하는 반례가 있었다.

4
-2 2
1 0
3 0
3 -1
4

로 입력이 주어졌을때 정답은

3

이 나와야 한다. 그러나 이 코드로는 정답이 2가 출력 되었다. 그 이유는 다음과 같다.
위 입력을 그림으로 그려보면 아래와 같다.

내 코드의 경우에는 끝점 순으로 최소힙을 이용해서 정렬하였는데, 그러다보니 (-2, 2)와 (-1, 2)보다 끝점이 더 짧은 (0, 1)을 먼저 탐색하기 때문에, (0, 1)과 (0, 3)만 카운트되어 정답에 (-1, 3)이 포함되지 못하였다.

그렇다면 반대로 시작점순으로 정렬하면 되지 않겠느냐고 생각해볼 수 있다. 그러나 이 경우에는 또 다른 엣지케이스로 인해 반례가 생기게 된다.

결국 혼자서 해결하지 못하고 답안을 참고하게 되었다.

import sys
import heapq

N = int(sys.stdin.readline())
possible_positions = []
positions = []

# 계산 편하게 하기 위해서 입력 값을 정렬한다.
for _ in range(N):
    positions.append(sorted(list(map(int, sys.stdin.readline().split()))))
d = int(sys.stdin.readline())

for position in positions:
    start, end = position
    # d보다 짧을 경우에만 possible_positions 리스트에 넣어준다.
    if end - start <= d:
        possible_positions.append(position)

# possible_postions 내 요소들을 끝점을 기준으로 정렬시켜준다.
possible_positions.sort(key= lambda x: x[1])

priority_queue = []
result = 0
# 리스트를 순회한다.
for possible_position in possible_positions:
    # 큐가 비어있는 상태이면 우선순위큐에 위치를 추가한다.
    if not priority_queue:
        heapq.heappush(priority_queue, possible_position)
    # 큐에 요소가 있다면, 큐가 시작하는 위치 < (끝점 - d) 일 경우 해당하는 요소를 pop 시킨다.
    else:
        while priority_queue[0][0] < possible_position[1] - d:
            heapq.heappop(priority_queue)
            if not priority_queue:
                break
        # 큐 시작점이 (끝점 - d) 안에 속할 경우, 우선순위큐에 추가한다.
        heapq.heappush(priority_queue, possible_position)
    result = max(result, len(priority_queue))

print(result)

큐에 다 넣어두고 꺼내써야겠다고만 생각하였는데, 이런식으로 구현해야겠다는 생각은 미처 하지 못했던것 같다. 같은 큐라도 보다 다양하게 적용할 수 있다는것을 배우게 되었다.