[ 백준 / G2 / 파이썬 Python ] 13334번 파이썬

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

13334번: 철로

 

코드

---

from heapq import heappop,heappush
n = int(input())
arr = sorted([sorted(list(map(int,input().split()))) for _ in range(n)], key=lambda x: x[1])
d = int(input())
answer = 0
heap = []
for s,e in [(x,y) for x,y in arr if (y-x) <= d]:
    while heap and heap[0][0] < e-d:
        heappop(heap)
    heappush(heap,(s,e))
    answer = max(answer,len(heap))
print(answer)

 

사용 알고리즘

---

" 라인 스위핑, 우선순위 큐 "

 

풀이

---

이전에도 비슷한 문제들을 몇 번 풀어보았지만 이게 라인스위핑이라는 알고리즘을 사용한다는 것은 알지 못했다.

 

라인 스위핑?

라인 스위핑은 공간이나 직선 상을 탐색할 때 전체 공간을 한 번에 스캔하며 마주치는 요소들에 대해 판단기준을 적용시켜 정답을 구하는 알고리즘이다.

대게 라인 위에 위치한 요소들의 개수가 너무 많아서 여러번 탐색하면 시간초과가 나기 때문에 사용한다.

 

이 문제도 n이 10만이기에 O(nlogn)까지는 괜찮지만 O(n^2)로 가면 시간초과가 날 것이라 완전탐색으로 해결할 수는 없었다.

따라서 한 번의 탐색안에서 기준을 적용시켜 정답을 도출해야 했다.

 

먼저 입력을 받는 부분을 살펴보자.

n = int(input())
arr = sorted([sorted(list(map(int,input().split()))) for _ in range(n)], key=lambda x: x[1])
d = int(input())

n과 d는 평범하게 받았지만 arr은 조금 다르다.

문제의 입력을 보면 요소들을 (시작,끝) 형태로 주어지지 않고 (끝,시작)의 형태 또한 섞여있다. 따라서 이 부분을 모두 한 형태로 고정하기 위해서 정렬하여 리스트에 넣었다.

또한, 모든 요소가 들어간 리스트를 끝지점을 기준으로 오름차순 정렬하였는데 이는 아래에서 같이 보도록 한다.

 

이제 한 번의 arr 탐색에서 문제를 해결하는 과정이다.

answer = 0
heap = []
for s,e in [(x,y) for x,y in arr if (y-x) <= d]:
    while heap and heap[0][0] < e-d:
        heappop(heap)
    heappush(heap,(s,e))
    answer = max(answer,len(heap))

이 문제의 핵심은 위에서 끝지점을 기준으로 오름차순 정렬하였다는 것이다.

탐색을 진행하며 현재 원소의 끝점부터 즉, 현재 원소를 포함하여 얼마나 많은 원소들을 d안에 포함시킬 수 있느냐를 판단하는 것이다.

 

그렇다면 d안에 포함되는가를 판단하기 위해서는 시작점이 (현재 원소의 끝점 - d)안에 존재하느냐를 보면 된다.

끝점을 기준으로 정렬하여 탐색하기 때문에 현재 원소 이전의 원소들의 끝점은 당연히 현재보다 작거나 같기 때문이다.

 

따라서 시작점으로만 보면 되는데 시작점은 끝점과 달리 정렬되어 있지 않기 때문에 heap 자료구조로 작은 것부터 빼준다.

heap의 첫 번째 원소가 heap안에 있는 원소들 중 가장 시작점이 작은 원소인데 이 원소가 d안에 포함될 때까지 heap에서 빼주면 현재 원소를 포함하여 d안에 포함되는 가장 많은 원소들을 구할 수 있다.

 

for s,e in [(x,y) for x,y in arr if (y-x) <= d]

이 부분은 heap에 원소를 넣는 과정에서 현재 원소의 (e-s)가 d보다 길 경우를 고려하지 않고 heap에 넣고 있기 때문에 설정하였다.

if문으로 설정해도 좋지만 간단하고 보기 좋아서 이렇게 적었다.