이 글에서는 크기가 서로 다른 K개의 정렬된 연결 리스트가 주어졌을 때, 이를 하나의 결과 리스트로 병합하는 방법을 다룹니다. 병합된 결과 리스트 역시 오름차순으로 정렬된 상태를 유지해야 하며, 최종적으로 사용자에게 출력됩니다.
예제로 이해하기
입력 −
int k = 3;
list[0] = new Node(11);
list[0].next = new Node(15);
list[0].next.next = new Node(17);
list[1] = new Node(2);
list[1].next = new Node(3);
list[1].next.next = new Node(26);
list[1].next.next.next = new Node(39);
list[2] = new Node(4);
list[2].next = new Node(8);
list[2].next.next = new Node(10);
출력 −
2>> 3>> 4>> 8>> 10>> 11>> 15>> 17>> 26>> 39>> null
설명 − 각각 정렬된 상태인 K개의 연결 리스트가 주어집니다. 병합 과정에서는 자바의 Comparator를 활용해 각 리스트의 헤드(첫 번째 노드)끼리 값을 비교하고, 작은 값부터 순서대로 결과 리스트에 연결합니다.
입력 −
int k = 2;
list[0] = new Node(1);
list[0].next = new Node(4);
list[0].next.next = new Node(5);
list[1] = new Node(2);
list[1].next = new Node(3);
list[1].next.next = new Node(6);
list[1].next.next.next = new Node(8);
출력 −
1>> 2>> 3>> 4>> 5>> 6>> 8>> null
풀이 접근 방식
병합할 리스트의 개수(K)를 입력받습니다.
연결 리스트의 노드를 생성하기 위한
Node클래스를 정의합니다.각 리스트를 정렬된 상태로 초기화한 뒤, 리스트 배열과 k를 매개변수로
mergeLists함수에 전달합니다.함수 내부에서는
Comparator를 기반으로 한PriorityQueue(최소 힙)를 생성하고, k개 리스트의 헤드 노드를 모두 힙에 추가합니다.힙이 빌 때까지 가장 작은 값을 가진 노드를 꺼내어(
poll) 결과 리스트의 뒤에 차례로 연결합니다.꺼낸 노드의
next노드가 존재하면, 그 노드를 다시 힙에 넣어 다음 후보로 관리합니다.이 과정을 반복하면 전체 노드가 오름차순으로 정렬된 단일 연결 리스트가 완성되며, 최종적으로 그 헤드를 반환합니다.
이 방식은 시간 복잡도가 O(N log K)로, N은 전체 노드의 개수, K는 리스트의 개수입니다. 매번 두 리스트씩 순차적으로 병합하는 방식보다 효율적입니다.
구현 예제
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
public class testClass {
public static Node mergeLists(Node[] list, int k) {
PriorityQueue<Node> priorityQueue;
priorityQueue = new PriorityQueue<Node>(Comparator.comparingInt(a -> ((Node) a).data));
priorityQueue.addAll(Arrays.asList(list).subList(0, k));
Node head = null, last = null;
while (!priorityQueue.isEmpty()) {
Node min = priorityQueue.poll();
if (head == null) {
head = last = min;
} else {
last.next = min;
last = min;
}
if (min.next != null) {
priorityQueue.add(min.next);
}
}
return head;
}
public static void main(String[] s) {
int k = 3;
Node[] list = new Node[k];
list[0] = new Node(11);
list[0].next = new Node(15);
list[0].next.next = new Node(17);
list[1] = new Node(2);
list[1].next = new Node(3);
list[1].next.next = new Node(26);
list[1].next.next.next = new Node(39);
list[2] = new Node(4);
list[2].next = new Node(8);
list[2].next.next = new Node(10);
System.out.println("The merged list is-->");
Node head = mergeLists(list, k);
while (head != null) {
System.out.print(head.data + ">> ");
head = head.next;
}
System.out.print("null");
}
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
The merged list is-->
2>> 3>> 4>> 8>> 10>> 11>> 15>> 17>> 26>> 39>> null
정리
K개의 정렬된 연결 리스트를 병합할 때는 PriorityQueue(최소 힙)를 활용하는 것이 가장 효율적입니다. 각 리스트의 현재 노드만 힙에 유지하면서 가장 작은 값을 꺼내 결과 리스트에 연결하는 방식으로, 전체 노드 수가 N이고 리스트 수가 K일 때 O(N log K)의 시간 복잡도로 문제를 해결할 수 있습니다.