목록2024/10/17 (1)

매일 조금씩

Leet code (Hard): 23. Merge k Sorted Lists - JAVA

합쳐야할 LinkedList가 두개가 아니다.여러개의 LinkedList를 전부 돌면서 하나하나 비교를 하는것은 매우 비효율적이고 방식도 복잡할 것이다.따라서, 전체 노드를 각각으로 보고 정렬시킨후 연결 시키는 방식으로 풀어내야한다.정렬을 위해선 PriorityQueue를 사용하는 것이 가장 효율적이다.Step1) 가장 먼저 value를 보고 정렬해주는 PriorityQueue를 생성해서,주어진 각 리스트의 헤드를 삽입한다. PriorityQueue에 한번 삽입할때의 시간복잡도는 O(log K)이다. (삽입할때마다 정렬하기때문)이걸 삽입하는 수만큼 반복하니 시간복잡도는 O(K log K) K: 리스트 수 이다.Step2)그리고 PriorityQueue를 poll() 하면서 연결하고, poll()된 노드의..
알고리즘/LinkedList 2024. 10. 17. 14:07
이전 Prev 1 Next 다음