📌 문제
- 여러 개의 ListNode가 들어있는 ListNode 배열이 주어진다. 해당 ListNode들을 오름차순으로 정렬해서, 새로운 노드를 만들어서 반환하라.
https://leetcode.com/problems/merge-k-sorted-lists/
📌 문제 풀이
- brute force로 풀어볼까 했으나, 딱 봐도 시간복잡도도 그렇고, 풀이도 좋지 못할 것 같다. 그리고 null 값이 들어올 수 있기 때문에, null check를 하는 것도 복잡하다.
- Heapq ( ProrityQueue ) 와 ListNode를 이용하면 쉽게 풀 수 있다.
- ListNode[] lists 의 값을 PriorityQueue 에 넣는다. 이 때의 Comparator ( 정렬기준 ) 은 Integer.compare( n1.val , n2.val ) 을 해주면 오름차순이 된다.
- pq가 null이 될 때까지 loop를 돌고, 값을 뺄 때 해당 노드의 다음 값이 null이 아니라면 다시 큐에 넣어준다.
📌 코드
public class Main {
public static void main(String[] args) {
ListNode li1 = new ListNode(1);
li1.add(4);
li1.add(5);
ListNode li2 = new ListNode(1);
li2.add(3);
li2.add(4);
ListNode li3 = new ListNode(2);
li3.add(7);
ListNode[] list = new ListNode[3];
list[0] = li1;
list[1] = li2;
list[2] = li3;
Solution solution = new Solution();
ListNode listNode = solution.mergeKLists(list);
listNode.print();
}
public static class ListNode {
Integer val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
// this 를 받을 방법을 못하고, next 로 조작하고 있었다.
void add(int val){
ListNode node = new ListNode(val);
ListNode n = this;
while(n.next !=null){
n=n.next;
}
n.next = node;
}
void print(){
ListNode node = this;
while(node.next!=null){
System.out.println(node.val);
node=node.next;
}
System.out.println(node.val);
}
}
static class Solution {
static Comparator<ListNode> comp = new Comparator<ListNode>() {
@Override
public int compare(ListNode o1, ListNode o2) {
return Integer.compare(o1.val,o2.val);
}
};
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>(comp);
for(ListNode node : lists){
if(node == null) continue;
pq.offer(node);
}
ListNode res = new ListNode(0);
ListNode temp = res;
while(!pq.isEmpty()){
ListNode poll = pq.poll();
if(poll.next != null) pq.offer(poll.next);
temp.next = poll;
temp = temp.next;
}
return res.next;
}
}
}
댓글