철로 - 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의 임의의 선분에 대하여, 집과 사무실 위치가 모두 그 선분에 포함되는 사람들의 최대 수를 한 줄에 출력한다.

풀이

하.... 진짜 답 보고도 한 3시간 걸렸다.

풀이 이전에, key=lambda x : .... 에 대해 얕 봤다가 뼈저리게 아팠다.
그냥 sort()인 줄 알고 넘겼는데, [ [s, e], [s, e], [s, e]... ]를 정렬하는 기준이 s가 아닌 e여야 했고, 그것은 그냥 sort()로는 당연히 해낼 수 없다.

람다함수

https://wikidocs.net/22804
def로 함수 선언을 하지 않고 일회용 함수를 선언하고 싶을 때 쓴다.
기본적으로 key=lambda x : ... 의 형태로 작성하면 되는 듯?

일단 sort()의 예만 봤다.
def로 함수를 선언하였을 땐, sort()는 이런 식으로 응용이 된다.
sort(key=원하는정렬기준을return하는함수)

그런데 def로 함수 선언하는 대신 아래와 같이 쓸 수도 있다는 것이다.
sort(key=lambda x : x를인자로받으며이에대해원하는정렬기준작성)

그래서 이 아래의 풀이에서, 우리는 e값을 기준으로 pop과 push를 거듭하므로 1차적인 힙을 구했을 때에 이를 "힙 요소의 두번째(인덱스1째)요소로" 정렬해야 한다.

아래 답안은 정답이다.

import sys
import heapq
input = sys.stdin.readline
N = int(input())
HO = []
for _ in range(N):
    HO.append(sorted(list(map(int, input().split()))))
D = int(input())
HOh = []
for i in range(N):
    heapq.heappush(HOh, HO[i])
# print(HOh) # HO는 이제 HOh이라는 이름의 힙이 되었다.

heap = []
for ho in HO: # ho == [start, end]
    if abs(ho[1]-ho[0]) <= D:
        heapq.heappush(heap, ho)
# heap에 1차적으로 거른 후보군을 넣는다. 집-사무실 거리가 D보다 먼 항목들은 선상 어디에 위치해도 D안에 못 들어오니까 먼저 거른 것.

# heap.sort() # WRONG!!! end값을 기준으로 정렬해야 한다!!!
heap.sort(key=lambda x : x[1])

cnt = 0
tmph = []
for ho in heap: # 이제 heap의 요소들을 하나하나 검열할 거다. 
    if not tmph:
        heapq.heappush(tmph, ho) # 1. 가장 먼저, heap의 요소를 tmph에 넣는다.
    else:
        while tmph[0][0] < ho[1] - D: # 2. s<=e-D == true면 후보군에서 pop된다.
        # heap 요소의 e를 기준으로, 현재 heap의 루트의 s가 ("heap의 첫번째 요소의 e" - D)보다 작거나 같은지 확인.
        # 말인즉 D의 위치가 heap의 첫번째 요소의 e에서 끝난단 가정하에, s가 D 안에 있는지 보는 거다.
            heapq.heappop(tmph) # 3-2. 만약 true면 tmph에서 뺀다. tmph의 루트를 바로 그 다음 요소로 갈아끼우는 것.
            if not tmph: # 5. tmph가 비로소 빈 힙이 되면 for문 종료.
                break
        heapq.heappush(tmph, ho) # 3-1. 만약 s<=e-D == false면 tmph에 넣는다.
    cnt = max(cnt, len(tmph)) # 4. 그런 식으로 tmph의 길이가 얼마까지 최대로 늘어나나를 측정하는 것!

print(cnt)

짧게 설명하면 우선 입력값들은 모두 [집, 사무실] 즉 [start, end]의 꼴을 한다. 이들 중 선분의 길이 D보다 더 멀리 떨어진 요소들을 1차적으로 거른다. 그것을 end값 기준으로 sort()한다.

이후, 이 오름차순 정렬된 힙 heap은 그 요소들이 순차적으로 임시보관함 힙 tmph에 담겼다 빼졌다를 반복하며 계속해서 end-D가 start이하인지 확인당한다. 그 검열되는 기준은 "현재 tmph의 루트" 즉 tmph의 첫번째 요소의 s이다.
<-- 반복문 돌려지고 있는 heap이 오름차순이기 때!문!에! ho in heap의 ho가 어느 순간 ho[1] - D일 때, tmph의 루트가 팝되고 그 담 요소가 루트가 된다.
그런 식으로 루트가 계속 순차적으로 바뀌며 그 검열의 기준이 옮겨가는 것. (직선그래프상에서 왼->오)

하..

아래는 주석 지운 버전이다.

import sys
import heapq
input = sys.stdin.readline
N = int(input())
HO = []
for _ in range(N):
    HO.append(sorted(list(map(int, input().split()))))
D = int(input())
HOh = []
for i in range(N):
    heapq.heappush(HOh, HO[i])

heap = []
for ho in HO:
    if abs(ho[1]-ho[0]) <= D:
        heapq.heappush(heap, ho)

heap.sort(key=lambda x : x[1])

cnt = 0
tmph = []
for ho in heap: 
    if not tmph:
        heapq.heappush(tmph, ho) 
    else:
        while tmph[0][0] < ho[1] - D:
            heapq.heappop(tmph)
            if not tmph:
                break
        heapq.heappush(tmph, ho)
    cnt = max(cnt, len(tmph))

print(cnt)

반례는 아래의 링크에서 찾을 수 있었다.
https://www.acmicpc.net/board/view/34595
4
1 4
1 4
2 5
3 4
3
ANSWER: 3