You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
- k 개의 연결리스트인 lists가 주어진다.
- 각 연결리스트는 오름차순으로 정렬되어있다.
- 모든 linked list를 하나의 정렬된 연결리스트로 merge한 후 리턴하라.
Merge k Sorted Lists - LeetCode
💥💥💥쉬울 줄 알았는데 ㅋㅋ.. Heap 을 생각하는 것 까진 쉬었으나, 본인이 Merge 구현을 매우 못함을 알게 되었다. 💥💥💥
- 문제풀이 : PQ(HEAP) 사용하기
- 두 개의 Sorted List를 Merge한다고 생각한다면
- Divide and Conquer로 sort했던 것을 생각하면, 길이가 1일 때 까지 divide한 후, 하나의 array를 생성하여, 둘 중 더 작은 것을 먼저 new array에 넣는 방식으로 진행 후, 두 array중 아직 원소가 남아있는 것을 마지막에 모두 넣는방식
- 이 문제 역시 위와같이 분할 정복으로도 풀 수 있겠으나, 그 경우 메모리 소비가 클 것으로 생각된다. 따라서 나는 PQ(Heap)을 사용하여, PQ에 이 연결리스트들의 모든 노드들을 담는 방식으로 하였다.
- 순회는 반드시 필요할 것이기 때문에
- PQ에 list의 모든 원소들을 넣고, PQ에서 원소를 꺼내도록 한다.
- 각 연결리스트를 순회 해야하기 때문에,
- 리스트의 개수 k는 최대 10000개 이고
- 각 리스트의 길이는 최대 500이기 때문에
- PQ에 넣을 원소의 개수는 총 500000이고
- PQ에 n개를 모두 넣었다가 빼는데 걸리는 시간복잡도는 O(nlogn)이다. 시간초과가 일어날 일은 없을 듯하다.
- 아 이문제는, 문제에서 정의한 ListNode라는게 따로 있다.
- 두 개의 Sorted List를 Merge한다고 생각한다면
import java.util.*;
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
int k = lists.length;
Queue<Integer> pq = new PriorityQueue<>();
for(ListNode start : lists){
if(start == null) continue;
System.out.println("START "+start);
// 연결리스트의 맨 첫 번째 원소를 pq에 넣는다.
System.out.println("NEXT "+start.next);
System.out.println("VAL "+start.val);
pq.add(start.val);
ListNode next = start.next;
System.out.println("TEST");
// 각 연결리스트를 순회하며 PQ에 원소를 넣는다 .
while(next != null){
System.out.println(next.val);
pq.add(next.val);
next = next.next;
}
}
int size = pq.size();
System.out.println("PQ SIZE "+size);
ListNode prev = null;
ListNode first = null;
// PQ에서 원소를 하나씩 꺼내서 새로운 연결리스트를 생성한다.
if(size>0) {
first = new ListNode(pq.poll());
prev =first;
for(int j=1;j<size;j++){
int curInt = pq.poll();
ListNode cur = new ListNode(curInt);
prev.next = cur;
prev = cur;
}
}
return first;
}
}
- 풀이를 보아하니, 다른 사람들은 두 List를 Merge 하며 sort하는 방식을 사용했다 —> 이게 Merge를 할 때 마다 새로운 list를 생성하는 거라 메모리가 많이 든다. 그래서 메모리 효율은 상위권으로 된 듯 하다.
위의 풀이를 조금 수정함
- Queue에 Integer를 넣고 있어서, Node를 다시 생성하는 시간이 걸리고 있다.
- 따라서 이런식으로 수정해 봄 : Node를 매 번 새로 생성하지 않고, 기존에 주어진 ListNode를 사용한다. 단, 기존의 ListNode에는 next값이 있을 수 있기 때문에, 이상한 연결이 생성될 수 있음.(cycle이 생길수도 있음.) 따라서 next는 꼭 null로 초기화할 것.
import java.util.*;
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
int k = lists.length;
Queue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>(){
@Override
public int compare(ListNode o1, ListNode o2){
return o1.val-o2.val;
}
});
for(ListNode start : lists){
if(start == null) continue;
System.out.println("START "+start);
// 연결리스트의 맨 첫 번째 원소를 pq에 넣는다.
System.out.println("NEXT "+start.next);
System.out.println("VAL "+start.val);
pq.add(start);
ListNode next = start.next;
System.out.println("TEST");
// 각 연결리스트를 순회하며 PQ에 원소를 넣는다 .
while(next != null){
System.out.println(next.val);
pq.add(next);
next = next.next;
}
}
int size = pq.size();
System.out.println("PQ SIZE "+size);
ListNode prev = null;
ListNode first = null;
if(pq.isEmpty()==false){
first = pq.poll();
first.next = null; //기존 값이 있기 때문.
prev = first;
// PQ에서 원소를 하나씩 꺼내서 새로운 연결리스트를 생성한다.
while(pq.isEmpty()==false){
ListNode cur = pq.poll();
cur.next = null; // 기존 값이 있기 때문.
prev.next = cur;
prev = cur;
}
}
return first;
}
}
Merge
처음엔, lists에 있는 리스트들을, 앞에서부터 두 개 씩 묶어가며 Merge한다. --> 시간이 엄청 걸렸다.
다른 사람 풀이중, merge하는 것을 2개 2개 2개 2개.. 그 후에는 4개 4개 4개.. 그리고 이것이 lists.length일 때 까지만 늘려가며 merge하는 방식을 사용함
생각 못했던 부분
- 두 리스트를 비교하고 , 아직 new list에 들어가지 않은 것이 있다면, 연결을 해주는 방식을
if(n1!=null)
ans.next = n1;
이런식으로 구현할 수 있다는 걸 생각하지 못했었다.
- 링크드 리스트 이기 때문에 n1 자체가 뒤에 연결된 리스트 모두를 갖고 있는 것이라 굳이 while문을 돌며 노드 하나씩을 다시 ans.next에 붙이는 작업을 하지 않아도 된다.
헷갈렸던 부분 : 연결리스트의 노드를 순회하기.
ListNode temp = n1;
ListNode ans = new ListNode();
// n1 list에 연결된 노드들을 순회하며,"하나씩" ans list에 연결하고자 할 때
while(temp != null){
ans.next = temp;
temp = temp.next;
ans = ans.next;
} - ans 변수도, 다음 순회를 새롭게 연결시켜주려면 ans.next로 값을 업데이트 시켜야함을 간과햇었다.
import java.util.*;
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
int k = lists.length;
if(k==0)return null;
if(k==1) return lists[0];
int interval = 1;
while (interval < lists.length) {
for (int i = 0; i + interval < lists.length; i = i + interval * 2) {
lists[i] = mergeList(lists[i], lists[i + interval]);
}
interval *= 2;
}
return lists[0];
}
public ListNode mergeList(ListNode n1,ListNode n2){
// 비어있는 것일 경우 : [] 이러면 참 좋은데, 예시 중에 [[],[1,2]] 이런 것도 있기 때문에 고려해야한다.
// 저기서 [[]]는 결국 null인 ListNode에 해당하기 때문이다.
if(n1==null)return n2;
else if(n2==null)return n1;
ListNode ans =new ListNode();
ListNode answer = ans;
while(n1!=null && n2!=null){
// INCREMENTING implement를 해야 함.
if(n1.val>n2.val){
ans.next = n2;
ans = ans.next;
n2 = n2.next;
}else{
ans.next = n1;
ans = ans.next;
n1 = n1.next;
}
}
// 어차피 n1이라하면, 남아있는 Linked List 전체를 갖고 있는 것이라, n1만연결하면됨.
if(n1!=null){
ans.next = n1;
}
if(n2 !=null){
ans.next = n2;
}
return answer.next;
}
}Merge 다른 사람 풀이방법 : 1ms 걸리는 것
#1. lists의 리스트 두 개 씩을 Merge하는 방법 (BAD)
ListNode l1 = lists[0];
ListNode l2 = null;
// lists에 있는 리스트들을, 앞에서부터 두 개 씩 묶어가며 Merge한다.
for(int i=1;i<k;i++){
l2 = lists[i];
ListNode result = mergeList(l1,l2);
l1 = result;
}
return l1;#2. lists의 list 두 개 씩을 Merge 하는 방법
- 이 그림과 같이, Merge Sort의 경우,
int interval = 1;
while (interval < lists.length) {
for (int i = 0; i + interval < lists.length; i = i + interval * 2) {
lists[i] = mergeList(lists[i], lists[i + interval]);
}
interval *= 2;
}#3. 둘의 차이는 무엇 ?
- 각 mergeList에서 수행되는 비교연산의 횟수가 달라진다.
- Merge를 할 때는, 두 List중 길이가 더 긴 list의 길이만큼의 비교연산이 수행된다고 볼 수 있다 (Worst Case)
- interval을 두고 하는 것은, merge하는 두 리스트의 개수가 비슷하다. 따라서 최악의 경우가 거의 나지 않을 수 있다.
- 하지만 #1.의 방법으로 할 경우, 항상 더 길어지는 결과 list를 원래 lists에 있던 길이가 작은 list와의 비교를 하며 매 번 엄청난 수의 비교연산을 수행하게 된다.
import java.util.*;
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
int k = lists.length;
if(k==0)return null;
if(k==1) return lists[0];
int interval = 1;
while (interval < lists.length) {
for (int i = 0; i + interval < lists.length; i = i + interval * 2) {
lists[i] = mergeList(lists[i], lists[i + interval]);
}
interval *= 2;
}
return lists[0];
}
public ListNode mergeList(ListNode n1,ListNode n2){
// 비어있는 것일 경우 : [] 이러면 참 좋은데, 예시 중에 [[],[1,2]] 이런 것도 있기 때문에 고려해야한다.
// 저기서 [[]]는 결국 null인 ListNode에 해당하기 때문이다.
if(n1==null)return n2;
else if(n2==null)return n1;
ListNode ans =new ListNode();
ListNode answer = ans;
while(n1!=null && n2!=null){
// INCREMENTING implement를 해야 함.
if(n1.val>n2.val){
ans.next = n2;
ans = ans.next;
n2 = n2.next;
}else{
ans.next = n1;
ans = ans.next;
n1 = n1.next;
}
}
if(n1!=null){
ans.next = n1;
}
if(n2 !=null){
ans.next = n2;
}
return answer.next;
}
}