우선순위 큐(힙) 백준 13334 철로 파이썬

라인 스위핑 문제 : 정렬된 어떤 자료에서 시간 복잡도를 줄일 수 있도록 선을 한 번만 훑으면서 최종 결과를 찾는 방식으로 되어있으며 우선순위 큐를 자주 사용

 

최종 코드

import sys
import heapq
input = sys.stdin.readline

def subway(ho,d):
    i=0
    while i < len(ho):
        if abs(ho[i][1]-ho[i][0])>d :
            i+=1
        else : 
            ho[i].sort() #아닐경우 재정렬
            home_office.append(ho[i])
            i+=1
        
    if len(home_office)>0 :
        home_office.sort(key=lambda x: x[1])

        line = [] #heap
        count =0
        for i in home_office:    
            if len(line)>0:
                while True:
                    try:
                        if line[0][0]>=(i[1]-d):
                            break
                        else : heapq.heappop(line)
                    except: 
                        break
                
                heapq.heappush(line,i)
    
            else :
                heapq.heappush(line, home_office[0])
       
            count = max(count, len(line))

        return count
    else :
        return 0


N = int(input())
ho = [list(map(int, input().split()))for _ in range(N)]
home_office=[] # remove함수로  ho 의 값을 제거하려 했으나 그럴경우 시간초과가 나서 home_office 리스트에 새로 저장
d = int(input())

print(subway(ho,d))

1. 도착 위치를 기준으로 오름차순 정렬

•  1-1 hoem과 office의 위치가 반대로 적힌 경우(ex.) home = 35 offiece =25 -> [35 25])도 있기 때문에 이경우는 제외하고 d의 길이보다 home, office사이의 거리가 작은 경우 home_office리스트에 새로 넣어준다.
  
  (처음에 ho에서 remove를 이용 d의 길이보다 큰 경우를 ho리스트에서 제외하려 했으나 이경우 remove 함수가 ho안의 원소들을 같은 값을 찾을 때까지 비교하여 지우게 되므로 시간 초과가 나는 일이 생겼다. 그래서 home_office 리스트를 새로 만들어서 저장해주었다.)
•  1-2 새로 정렬한 home_office리스트의 길이가 0보다 크다면 line이 최대가 되는 수를 세고 0이거나 0보다 작다면
  d보다 라인이 작은 경우가 없다는 경우이므로 0을 출력하도록 한다.

 

2. Line의 최대 개수 찾기 (heap 정렬 이용 top을 비교)

출처 : https://chanhuiseok.github.io/posts/baek-28/

• home_office를 오른쪽 원소를 기준으로 정렬(오름차순)을 해준다.
  
  
• 오른쪽 원소를 기준으로 차례대로 home_office의 원소들의 길이를 검사하여 기준이 되는 점의 오른쪽으로부터 d보다 작은 경우는 heappop을 해주고 아닌 경우 heappush를 해준다
  
  
• heappush와 heappop으로 추가와 삭제를 할 경우 동시에 heap 정렬을 해주게 되어 line리스트에 쌓이는 top은 항상 왼쪽 값이 min 은값이 오게 된다.
  따라서 line [0][0] 원소는 항상 작은 값이 오게 되어 비교하게 되는 home_office의 원소(i)의 오른쪽[1]에서 d를 뺀 값보다 작으면  d의 길이를 넘어선단 이야기 이므로  heappop을 해주고
  아닐 경우 line [0][0]의 뒤의 값들은 모두 d안에 들어온다는 소리이므로 다음 home_office의 원소를 기준으로 반복한다.
  except를 쓴 이유는 heappop을 할 경우가 없는 경우 오류가 생기므로 이경우를 예외처리하기 위함이다.
  

  

각 비교마다 저장된 line리스트의 길이를 이전 리스트 길이 (count)와 비교해 큰 값을 다시 count에 저장해주고

마지막에 count를 리턴해주면 끝.