heapq와 PriorityQ 사이에는 연산속도의 차이가 극명하다. 우선순위 큐 자체가 힙큐를 기반으로 되어있기 때문
검색 시 확인 한 점.
우선순위 큐는 힙구조이지만 완전한 정렬상태.
힙큐는 힙의 형태 유지 (자식간의 크기 차 분별 불가)로 알고있음.
처음에는 작은 값이 산개해야 하는 것으로 보였으나,
13537 같은 예시를 통해 아닌 것을 알았음
더하는게 중복되는 구조가 아니면 되는 것 같아 완전이진트리의 형식으로 생각하다 힙을 생각했고
그에 따라 우선순위큐를 생각했다.
처음에는 그냥 무지성으로 팝2번씩만 해서 노드의 갯수자체를 1/2토막씩 내서 했으나
예시와 값이 달라 무조건 작은 파일 2개씩을 중복해서 합쳐야 할 것으로 판단
원래는 priorityqueue만 임포트해서 썼는데 구글링해보니 heapq랑 속도 30배 차이가 난다는 실험이 있길래 참고.
heapq로 진행했더니 바로 정답이었음.
*앞으로 ps는 힙큐를 쓰자.
42Seoul