[BOJ 13334, Python 3] 철로

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

13334번: 철로

 

 

풀이

일단 문제를 풀려면 정렬을 해야한다는 것을 아실 수 있는데, 그리디 알고리즘 문제를 좀 푸셨다면 큰 값을 기준으로 오름차순 정렬해야 한다는 것을 알 수 있습니다.

이런 아이디어를 사용하는 그리디 문제에서 가장 기초적인 문제는 이 문제(풀이)가 있습니다. 문제에서 구하는 것은 좀 다르지만 아이디어는 비슷하죠

이렇게 정렬을 한 뒤엔 이제 철로의 길이만큼 사람들을 받다가, 철로의 길이가 벗어나게 되면 집과 사무실의 위치중 작은 값을 가진 사람들을 빼서 d보다 작은 값을 유지하게 만들어주면 됩니다.

이때 빼는 방법은 우선순위큐를 이용하면 됩니다.

 

 

 

코드

from heapq import *
input = __import__('sys').stdin.readline
n = int(input())
arr = []
for i in range(n):
    arr.append(sorted([*map(int, input().split())]))
d = int(input())
 
ans = 0
arr.sort(key=lambda x: [x[1], x[0]])
people = []
for i in range(n):
    if arr[i][1] - arr[i][0] <= d:
        while people:
            person = heappop(people)
            if arr[i][1] - person[0] <= d:
                heappush(people, person)
                break
        heappush(people, arr[i])
        ans = max(ans, len(people))
print(ans)