알고리즘

[Python] 백준 13334번 철로

하루설렘 2021. 11. 17. 15:13

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

집과 사무실을 통근하는 n명의 사람들이 있다. 각 사람의 집과 사무실은 수평선 상에 있는 서로 다른 점에 위치하고 있다. 임의의 두 사람 A, B에 대하여, A의 집 혹은 사무실의 위치가 B의 집 혹은 사무실의 위치와 같을 수 있다. 통근을 하는 사람들의 편의를 위하여 일직선 상의 어떤 두 점을 잇는 철로를 건설하여, 기차를 운행하려고 한다. 제한된 예산 때문에, 철로의 길이는 d로 정해져 있다. 집과 사무실의 위치 모두 철로 선분에 포함되는 사람들의 수가 최대가 되도록, 철로 선분을 정하고자 한다.

양의 정수 d와 n 개의 정수쌍, (hi, oi), 1 ≤ i ≤ n,이 주어져 있다. 여기서 hi와 oi는 사람 i의 집과 사무실의 위치이다. 길이 d의 모든 선분 L에 대하여, 집과 사무실의 위치가 모두 L에 포함되는 사람들의 최대 수를 구하는 프로그램을 작성하시오.

그림 1. 8 명의 집과 사무실의 위치

그림 1 에 있는 예를 고려해보자. 여기서 n = 8, (h1, o1) = (5, 40), (h2, o2) = (35, 25), (h3, o3) = (10, 20), (h4, o4) = (10, 25), (h5, o5) = (30, 50), (h6, o6) = (50, 60), (h7, o7) = (30, 25), (h8, o8) = (80, 100)이고, d = 30이다. 이 예에서, 위치 10 과 40 사이의 빨간색 선분 L이, 가장 많은 사람들에 대하여 집과 사무실 위치 모두 포함되는 선분 중 하나이다. 따라서 답은 4 이다.

 

입력

입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,000이하의 서로 다른 정수이다. 마지막 줄에, 철로의 길이를 나타내는 정수 d (1 ≤ d ≤ 200,000,000)가 주어진다.

 

출력

출력은 표준출력을 사용한다. 길이 d의 임의의 선분에 대하여, 집과 사무실 위치가 모두 그 선분에 포함되는 사람들의 최대 수를 한 줄에 출력한다. 

나의 풀이

N이 100,000이기 때문에, O(NlogN)으로 푸는 방식으로 생각해야겠다. (명확한 기준은 아직 모르겠지만, 느낌적인 느낌)..

특정 마지막 위치에서 d라는 반경 안에 들어오는 case들을 모두 확인하려면 O(N^2)이다. 하지만 최소값들로만 확인하면 pop을 해주면, 이후에는 해당 요소를 확인할 필요가 없어지니 O(NlongN)으로 가능할 것이다. 

  • heapq.heappush(array, value) : array에 value를 넣어주면서 최소 힙상태로 만들어준다. <O(logN)>
  • heapq.heappop(array) : array[0] 즉 최소값을 array에서 pop해준다. <O(1)>
import sys
import heapq

n = int(sys.stdin.readline())
commute = []
for i in range(n):
    x, y = map(int, sys.stdin.readline().split())
    if x > y:
        x, y = y, x
    commute.append((x,y))
commute = sorted(commute, key=lambda x: x[1])
# location마다의 거리가 좁은건 제외
d = int(sys.stdin.readline())
ans = 0
possible = []
for location in commute:
    if location[1] - d > location[0]:
        continue
    else:
        heapq.heappush(possible, location)
        # 가능한건 최소힙에 저장한다.
    while possible[0][0] < location[1] - d:
        heapq.heappop(possible) 
        # 옮길때마다 삭제해야하는건 삭제한다. 
    ans = max(ans, len(possible))
# len(possible)최대가 될때마다 갱신한다. 

print(ans)

 

 

※ 사소한 실수는 반복하지 말자

>>> a = [1,3,2,4]
# (오답) 변수에 대입을 안하면 기존 변수는 기존값 그대로
>>> sorted(a,reverse=True)
[4, 3, 2, 1]
>>> a
[1, 3, 2, 4]
# (정답) 변수에 대입해야 변경된다. 
>>> a = sorted(a, reverse=True)       
>>> a
[4, 3, 2, 1]

# (추가) 이렇게 하면 별도 변수대입이 필요없다. 
>>> a = [1, 2, 3, 4]
>>> a.sort(reverse=True)
>>> a
[4, 3, 2, 1]

 

※ 공부하는 블로그로 잘못된 내용이 있다면 댓글에 알려주시면 수정하겠습니다. 감사합니다.