[백준]13334 철로 [Python]

 

 

이 문제는 우선 순위 큐를 활용해서 푸는 문제입니다.

 

처음에는 어떤 방식으로 큐에 넣어서 가장 많이 포함하는 부분을 구하는지와 두번째 값 기준으로 오름차순 정렬을 하는 부분에서 시간을 많이 소요했습니다.

 

우선 list에 입력값을 받아 sorted함수를 통해서 첫번째 값을 기준으로 오름차순 정렬을 한다음, lambda함수를 사용해서 두번쨰 값 기준으로 정렬을 한번더 해줍니다.

 

아래 코드는 위에 정렬된 h_o 리스트에서 각 선분의 길이가 철로의 길이(d)보다 긴 값들을 제거해주는 코드입니다.

 

위의 코드는 파이썬에서 우선순위 큐에 자주사용하는 heapq 를 사용해서 heap 리스트에 h_o_list 리스트값을 하나씩 넣고 heap의 길이의 최대값을 answer에 저장해서 마지막에 최대 카운트를 가져올 수 있는 방법입니다.

 

heap에 들어있는 heap[0][0]의 길이보다 넣고자하는 j의 값에서 철로의 길이를 뺀값보다 작은경우 heappop을 통해 다른 경우의 수를 다 확인합니다.

 

전체 코드입니다.