[알고리즘] 크래프톤 정글 1주차 / 알고리즘 中 혼자서 못 푼 문제 정리3(철로)

BOJ 13334 철로

난이도 : (크래프톤 정글 기준) 상, (백준 난이도 기준) 골2

사용 알고리즘 or 자료 구조 : 우선순위 큐, 힙

처음 생각한 풀이

Min heap, Max heap을 각각 선언하여 Min heap에는 시작점을 기준으로, Max heap에는 끝 점을 기준으로 입력 값들을 튜플로 넣어준다.

 

그 후 Min heap의 첫번째 원소와 Max heap의 첫번째 원소의 차이를 dist라 하고 dist와 입력받은 d를 비교하여 d가 더 크다면 전체 인원, 아니라면 그 다음 과정이 시작된다.

 

각 순회마다 이전의 Min heap의 원소와 지금의 Min heap의 차이, 이전의 Max heap의 원소와 지금의 Max heap의 원소의 차이를 비교한다.

 

둘 중 차이가 더 큰 쪽을 선택하여 Max heap이 선택됐다면 이전의 Max heap 원소를 아예 제거하는 방식으로 사람을 제거하면서 순회를 반복한다.(이 경우 가장 오른쪽에 위치한 사람 제거)

 

하지만 이 풀이대로라면 시작점이 같거나 끝점이 같은 사람들을 고려하지 못하여 해결할 수 없었다.

구글링 이후 풀이

아무리 생각해도 답이 떠오르지 않아해서 정답을 구글에 찾아보았다.

 

풀이 방법을 다른 사람들과 논의할 때 장난식으로 '이거 20줄 안에 끝나는거 아니에요?' 했는데 정말이었다.

 

접근법 방법 자체는 단순하다.

 

처음 사람들의 시작점, 끝점을 입력받을 때 힙이 아닌 리스트에 입력을 받고 그 리스트를 정렬시켜준다.

이 때, 정렬 기준은 뒤의 요소 기준으로 오름차순으로 하고 만약 같다면 앞의 요소 기준으로 오름차순으로 정렬시킨다.

 

Min heap을 선언해주고 리스트 순회가 시작된다. 이 풀이과정에서는 사람들의 시작점이 아닌, 끝점을 기준으로 모든 것을 해결한다.

 

각 순회마다 이번 차례의 사람의 끝점을 기준으로 d(철로 길이)를 빼주어 기준점을 잡아준다. 그 후, 이번 차례의 사람의 시작점을 Min heap에 push해준다.

 

push가 되었다면 바로 while문이 시작된다. while 문의 조건은 다음과 같다.

1) Min heap이 비어있는지 확인

2) Min heap의 첫번째 요소가 앞서 정한 기준점보다 작은지 확인

이 두가지 경우가 통과되면 Min heap에서 요소를 제거한다.

 

while문을 모두 돌았다면 기준점 밖에 있는 사람들은 Min heap에서 모두 제거된 상태이다.

이 때의 Min heap 크기와 max값을 비교해주어 max값을 갱신한다.

 

이 풀이 방법대로면 O(nlogn)만에 실행이 끝난다.

 

 

 

 

 

 

 

 

 

※ 스 포 주 의 ※

 

 

 

 

코드

import sys

import heapq

N = int(sys.stdin.readline())

li = []

for i in range(N):

    a, b = map(int,sys.stdin.readline().split())

    li.append([min(a, b), max(a, b)])

d = int(sys.stdin.readline())

li.sort(key = lambda x : (x[1], x[0]))

### 사람들 집~회사를 더 뒤에 있는거 기준으로 오름차순, 같다면 앞에 있는거 기준으로 오름차순

hq = []

ans = 0

for i in range(N):

    start_point = li[i][1] - d

    ### end_point를 기준으로 d 만큼 뺀 것을 기준으로 삼음

    heapq.heappush(hq, li[i][0])

    ### min heap에 지금 사람의 집(start 지점)을 넣음

    while hq and hq[0] < start_point:

        ### min heap이 비어있지 않고, min heap의 첫번째 값이 기준점보다 앞에 있다면 min heap에서 제거

        heapq.heappop(hq)

    ### min heap 안에 있는 점들은 현재 기준점보다 뒤에 있으므로 더 처리 해줄게 없음

    ans = max(ans, len(hq))

    ### heap의 크기와 현재 정답을 비교

print(ans)