[Grind75-LeetCode] Merge k Sorted Lists - Hard
접근
- 우선순위 큐
- 분할 정복
- 버킷 정렬
풀이
ListNode 객체를 정렬된 상태로 병합하는 문제이다. ListNode 객체는 필드로 값과 다음 ListNode의 참조 값을 가지고 있다. 이 문제를 봤을 때 주어진 노드의 순서를 알 맞게 배열해 하나의 ListNode로 만들어라는 말이겠지만 과연 채점 기준으로 객체의 참조값을 비교해 볼까?라는 생각이 들었다. 만약 참조 값을 기준으로 채점하지 않는다면 그냥 값들을 순서에 맞게 새로운 객체를 만든 뒤 반환하면 되기 때문이다. 코드가 복잡하지 않으니 한 번 해봤다.
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (ListNode node : lists) {
while (node != null) {
pq.offer(node.val);
node = node.next;
}
}방법은 그냥 우선순위 큐에 모든 값들을 다 넣은 뒤 하나씩 뽑아 노드를 연결해 주는 것이었다.
if (pq.isEmpty()) {
return null;
}
ListNode result = new ListNode(pq.poll());
ListNode pointer = result;
while (!pq.isEmpty()) {
pointer.next = new ListNode(pq.poll());
pointer = pointer.next;
}
return result;
}만약 큐가 비었다면 주어진 값이 존재하지 않아 null을 반환하면 되는데 미리 List의 길이가 0이거나 null이면 null을 반환하는 코드를 처음에 넣었는데 [ [ ], [ ] ] 이 예시처럼 값은 비었지만 길이가 0 아닌 경우도 있었고 생각보다 다양한 케이스가 있길래 그냥 큐에 넣어진 값이 없다면 null을 반환하게 했다. 그리고 만들어진 큐에서 값을 뽑아 새로운 객체를 만들어 반환했다.
결과는 통과가 되었다. 객체의 참조 값을 기준으로 비교하지 않고 값을 통해 비교가 이루어지는 것인지 통과는 했지만 매번 새로운 객체를 생성해야 한다는 점과 정확하게는 주어진 객체와 전혀 다른 객체를 반환했다는 점에서 편법을 통해 통과한 것이라고 볼 수 있다.
분할 정복
주어진 객체를 실제로 비교해 연결을 시키기 위해선 분할 정복을 통해 병합을 했다. 주어진 리스트를 절반으로 나누어 두 개씩 묶어 병합을 순차적으로 진행하는 것이다.
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
if (lists.length == 1) {
return lists[0];
}
int mid = lists.length / 2;
ListNode left = mergeKLists(Arrays.copyOfRange(lists, 0, mid));
ListNode right = mergeKLists(Arrays.copyOfRange(lists, mid, lists.length));
return merge(left, right);
}분할 정복의 코드이다. lists를 반으로 나누어 가며 병합을 진행하게 된다.
lists = [[1,4,5],[1,3,4],[2,6]]
mergeKLists(lists){
//실제 lists는 길이가 3으로 ListNode가 3개 들어있음
lists = [ListNode, ListNode, ListNode]
//분할 mid = 3(length) / 2 = 1
leftLists = mergeKLists([lists[0], lists[1]])
rightLists = mergeKLists([lists[2]])
//리스트를 반으로 나누며 다시 재귀 수행
}
mergeKLists(leftLists lists){
//재귀로 리스트 분할
lists = [lists[0], lists[1]]
mid = 2(length) / 2 = 1
left = mergeKLists(lists[0])
right = mergeKLists(lists[1])
//분할 된 lists의 길이가 1이 될 때 까지 실행
//lists의 길이가 1이라면 mergeKLists의 if (lists.length == 1) 조건 검사로 인해 return lists[0] 반환
//각각 1개의 ListNode가 반환되면 merge(left, right) 실행 후 병합된 ListNode 반환
}위와 같은 과정으로 각각 left, right가 한 개의 ListNode가 반환될 때까지 분할을 수행한 뒤 반환된 두 노드를 하나의 노드로 병합하여 반환을 모든 노드가 병합될 때까지 반복한다.
private ListNode merge(ListNode n1, ListNode n2) {
ListNode dmy = new ListNode(0);
ListNode node = dmy;
while (n1 != null && n2 != null) {
if (n1.val < n2.val) {
node.next = n1;
n1 = n1.next;
} else {
node.next = n2;
n2 = n2.next;
}
node = node.next;
}
if (n1 != null) node.next = n1;
if (n2 != null) node.next = n2;
return dmy.next;
}두 노드를 병합하는 과정이다. 두 노드가 null이 아니라면 값을 비교해 병합을 수행하는 과정으로 만들어진 더미 노드의 다음 포인터로 연결하여 노드를 다시 재배열 한 뒤 병합이 완료된 첫 노드를 반환해 주게 된다.
버킷 정렬
버킷 정렬이란 데이터를 여러 개의 버킷으로 나누어 각 버킷에 대한 정렬을 수행한 뒤 모든 버킷을 병합하여 최종적으로 결과를 얻는 방식이다. 제일 성능이 좋았던 코드로 각 리스트 노드들을 값으로 분류해 배열의 인덱스에 똑같은 값끼리 미리 연결해 둔 뒤 해당 배열을 순차적으로 돌며 연결해 주는 방법이었다.
lists = [[1,4,5],[1,3,4],[2,6]]
table[1] = ListNode.val(1) - ListNode.val(1)
table[2] = ListNode.val(2)
table[3] = ListNode.val(3)
table[4] = ListNode.val(4) - ListNode.val(4)
table[5] = ListNode.val(5)
table[6] = ListNode.val(6)위와 같은 방식으로 미리 각 값에 맞게 연결해 둔 뒤 table [1]부터 순차적으로 연결해 정렬된 리스트를 얻는 방식이다.
public ListNode mergeKLists(ListNode[] lists) {
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
for (ListNode list : lists) {
while (list != null) {
int val = list.val;
if (val > max) {
max = val;
}
if (val < min) {
min = val;
}
list = list.next;
}
}우선 ListNode를 돌며 최댓값과 최솟값을 구하는 과정이다. 최대 최솟값이 왜 필요한 지는 뒤에서 나온다.
ListNode[] table = new ListNode[max - min + 1];
for (int i = lists.length - 1; i >= 0; i--) {
ListNode node = lists[i], temp;
while (node != null) {
temp = node.next;
node.next = table[node.val - min];
table[node.val - min] = node;
node = temp;
}
}각 버킷에 값들을 연결하는 과정이다. 사실 최대 최솟값 없이 최댓값만 구한 뒤 값에 맞는 인덱스에 값들을 매핑하면 알아보기도 편하고 하겠지만 그럴 경우 낭비되는 공간과 뒤에 연결 과정에서 불필요한 연산이 많이 발생할 수 있기 때문이다. 예를 들어 최댓값은 100이지만 나머지 값들은 다 1,2,3 정도로 작은 값만 존재한다면 중간에 90개가 넘는 불필요한 공간이 생성되고 뒤에 연결하는 연산에서 또한 90개의 불필요한 배열 공간을 탐색해야 한다. 그런 일을 방지하기 위해 최댓값에서 최솟값을 뺀 뒤 1을 더해 최소한의 크기로 배열을 사용하며 낭비를 줄이는 것이다. 그 외에는 최솟 값으로 인해 계산된 인덱스에 각 값들을 연결하는 과정이다.
ListNode result = new ListNode();
ListNode pointer = result;
for (ListNode node : table) {
if (node != null) {
pointer.next = node;
pointer = pointer.next;
while (node.next != null)
node = node.next;
pointer = node;
}
}
return result.next;버킷에 매핑이 다 되면 버킷들을 순서대로 연결하게 되는데 버킷 연결 후 포인터를 연결한 버킷의 마지막 노드로 맞춰줘야 다음 노드를 연결할 때 문제가 되지 않는다.
전체 코드
우선순위 큐
/**
* 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) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (ListNode node : lists) {
while (node != null) {
pq.offer(node.val);
node = node.next;
}
}
if (pq.isEmpty()) {
return null;
}
ListNode result = new ListNode(pq.poll());
ListNode pointer = result;
while (!pq.isEmpty()) {
pointer.next = new ListNode(pq.poll());
pointer = pointer.next;
}
return result;
}
}
분할 정복
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
if (lists.length == 1) {
return lists[0];
}
int mid = lists.length / 2;
ListNode left = mergeKLists(Arrays.copyOfRange(lists, 0, mid));
ListNode right = mergeKLists(Arrays.copyOfRange(lists, mid, lists.length));
return merge(left, right);
}
private ListNode merge(ListNode n1, ListNode n2) {
ListNode dmy = new ListNode(0);
ListNode node = dmy;
while (n1 != null && n2 != null) {
if (n1.val < n2.val) {
node.next = n1;
n1 = n1.next;
} else {
node.next = n2;
n2 = n2.next;
}
node = node.next;
}
if (n1 != null) node.next = n1;
if (n2 != null) node.next = n2;
return dmy.next;
}
}
버킷 정렬
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
for (ListNode list : lists) {
while (list != null) {
int val = list.val;
if (val > max) {
max = val;
}
if (val < min) {
min = val;
}
list = list.next;
}
}
ListNode[] table = new ListNode[max - min + 1];
for (int i = lists.length - 1; i >= 0; i--) {
ListNode node = lists[i], temp;
while (node != null) {
temp = node.next;
node.next = table[node.val - min];
table[node.val - min] = node;
node = temp;
}
}
ListNode result = new ListNode();
ListNode pointer = result;
for (ListNode node : table) {
if (node != null) {
pointer.next = node;
pointer = pointer.next;
while (node.next != null)
node = node.next;
pointer = node;
}
}
return result.next;
}
}'알고리즘 > 코딩테스트-Grind75' 카테고리의 다른 글
| [Grind75-LeetCode] Largest Rectangle in Histogram JAVA (0) | 2024.12.07 |
|---|---|
| [Grind75-LeetCode] Maximum Profit in Job Scheduling JAVA (0) | 2024.12.05 |
| [Grind75-LeetCode] Basic Calculator JAVA (0) | 2024.12.04 |
| [Grind75-LeetCode] Word Ladder JAVA (0) | 2024.12.03 |
| [Grind75-LeetCode] Find Median from Data Stream JAVA (0) | 2024.11.30 |