성능 요약
메모리: 128048 KB, 시간: 416 ms
분류
자료 구조, 우선순위 큐, 정렬, 스위핑
문제 설명
집과 사무실을 통근하는 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의 임의의 선분에 대하여, 집과 사무실 위치가 모두 그 선분에 포함되는 사람들의 최대 수를 한 줄에 출력한다.
아이디어, 문제풀이
- 이 코드는 다음과 같이 동작한다.
- 각 집과 사무실의 좌표를 입력 받고, 작은 좌표를 왼쪽에 두도록 정렬하여 리스트에 추가합니다.
- 철로의 길이를 입력 받습니다.
- 리스트를 오른쪽 좌표 기준으로 정렬합니다.
- 힙 자료구조를 사용하여 왼쪽 좌표를 저장하고 철로 안에 있는 집과 사무실을 카운트합니다.
- 현재 철로의 범위에서 벗어난 좌표를 힙에서 제거하고 카운트를 최댓값으로 업데이트합니다.
TROUBLE SHOOTING
- 초반에는 힙을 안쓰고 구현할수 있을줄 알았다.
아래는 chat gpt의 일침 ;ㅁ; 풀어서 다시 해석해보자면, 시작점과 끝점만을 비교하게되면 애매한 위치에 걸친 철로들을 절대 고려할수 없다. 로 정리할 수 있다.import heapq import sys input = sys.stdin.readline n = int(input()) n_list = [] for i in range(n): h, o = map(int, input().split()) n_list.append([h,o]) d = int(input()) n_list.sort() print(n_list) # print(min(n_list) # print(heapq.heappop(n_list)) now_count = 0 for i in range(len(n_list)): target_start = i target_end = target_start + d print(target_start) print(target_end) for j in range(len(n_list)): count = 0 if target_start >= n_list[j][0] and target_end <= n_list[j][1]: count += 1 else: break result = max(count, now_count) now_count = count print(result) print(result)#이 코드는 여전히 문제의 요구 사항을 정확하게 충족하지 않습니다. 주요 문제점은 다음과 같습니다: #1. n_list를 정렬하지 않고 시작하므로 각각의 철로의 위치를 올바르게 고려하지 않습니다. #2. count 변수가 이중 반복문 안에서 초기화되지 않아, # 이전 철로 위치에 대한 카운트가 현재 철로 위치의 카운트에 누적됩니다. #3. 이중 반복문을 사용하여 모든 가능한 철로 위치를 확인하는 것이 아니라, # 철로의 왼쪽 끝을 각 사무실의 위치로만 설정합니다. # 따라서 다른 가능한 철로 위치를 고려하지 못할 수 있습니다. # 이러한 문제점들로 인해 이 코드는 문제의 요구 사항을 정확하게 충족하지 않습니다. # 이전에 제시한 코드를 사용하시면 문제를 올바르게 해결할 수 있습니다. # 아래 코드를 다시 참조하시기 바랍니다. #철로의 왼쪽 끝을 각 사무실의 위치로만 설정하는 대신, target_start = i로 설정합니다. # 이렇게 하면 철로의 위치를 올바르게 고려하지 못할 수 있습니다.
- 해맸던 파트를 주석을 달아서 설명해봤다.
# 현재 사무실(h)과 집(o) 사이의 거리가 주어진 철로의 길이(d)보다 작거나 같은 경우 if end - start <= d: # 시작 위치(start)를 최소 힙(pq)에 추가합니다. heapq.heappush(pq, start) # 철로의 오른쪽 끝(end)과 철로의 길이(d)의 차이보다 작은 시작 위치(start)가 pq에 있는 동안 while pq and pq[0] < end - d: # 최소 힙(pq)에서 가장 작은 시작 위치(start)를 제거합니다. heapq.heappop(pq) # 철로 안에 들어가는 집의 최대 개수를 구하기 위해 이전 최대 개수와 pq의 크기를 비교하여 큰 값을 저장합니다. count = max(count, len(pq))
- 같은 반 팀원이 작성한 코드인데, 생각보다 유용한것 같다. 내 코드에는 적용하지 않았지만, 주어진 철로길이보다 긴 철로들을 미리 배제하는 코드인데, 시간 단축에 도움이 될거같다.
for i in startend: if i[1] - i[0] <= d: abileroute.append(i)
- 아직 해결이 안된 부분이 있는데, 이 문제는 일단 미해결로 남겨두겠다.
왜 x[1]로 정렬하는걸까? x[0]으로 하면 안되는건가? 에 대한 질문인데, 정말 거짓말안치고 그 누구도 완벽한 답변을 제시하지 못했다. 구글링은 물론 chat gpt까지… 그래도 지금까지 생각해본것중 가장 가능성이 높은걸 생각해보면, “끝점으로 지정해야 코드를 좀더 효율적으로 구성할수 있다” 였다. 모두가 x[1]로 해놓고 풀길래 무조건 그렇게 해야하는줄 알았는데… 그건 아니였던것 같다 정도로 마무리 하려고 한다. 나중에 답을 얻을 지식이 생긴다면 수정하러 오겠다 🙂#x[1]을 기준으로 정렬하겠다. n_list.sort(key=lambda x: x[1])
코드
#https://www.acmicpc.net/problem/13334
#철로
#13334
import sys
import heapq
input = sys.stdin.readline
n = int(input())
n_list = []
for i in range(n):
h, o = map(int, input().split())
n_list.append((min(h, o), max(h, o)))
d = int(input())
#x[1]을 기준으로 정렬하겠다.
n_list.sort(key=lambda x: x[1])
print(n_list)
count = 0
pq = []
#start = h / end = o 값
for i in range(n):
start, end = n_list[i]
if end - start <= d:
heapq.heappush(pq, start)
while pq and pq[0] < end - d:
heapq.heappop(pq)
count = max(count, len(pq))
print(count)