문제 설명
이 문제에서는 세 가지 요소, 즉 데이터 값(data), 다음 노드를 가리키는 next 포인터, 그리고 임의 포인터(arbit)를 가지는 연결 리스트가 주어집니다. 우리가 해야 할 일은 각 노드의 임의 포인터가 자신보다 큰 값들 중 가장 작은 값, 즉 '다음으로 큰 값'을 가진 노드를 가리키도록 만드는 것입니다.
예를 들어 연결 리스트가 8 → 12 → 41 → 54 → 76 순으로 구성되어 있다면, 임의 포인터는 8이 12를, 12가 41을, 41이 54를, 54가 76을 가리켜야 합니다. 마지막 노드인 76보다 큰 값은 없으므로 NULL을 가리키게 됩니다.
해결 접근 방식
이 문제는 병합 정렬(Merge Sort) 알고리즘을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 임의 포인터(arbit)를 정렬 대상 리스트의 주요 연결 포인터로 취급합니다.
- 이 arbit 포인터 체인 위에서 병합 정렬을 수행하면, 노드들이 데이터 값의 오름차순으로 arbit를 통해 다시 연결됩니다.
- 정렬이 완료되면 각 노드의 arbit 포인터는 자연스럽게 자신보다 큰 값 중 가장 작은 값, 즉 다음으로 큰 값을 가진 노드를 가리키게 되어 문제가 해결됩니다.
이 방법의 시간 복잡도는 O(n log n)이며, 새로운 노드를 생성하지 않고 기존 포인터만 재배열하므로 추가 공간은 재귀 호출 스택 정도(O(log n))만 필요합니다.
구현 예제
위 접근 방식을 C++로 구현한 프로그램입니다.
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* next, *arbit;
};
Node* SortedMerge(Node* a, Node* b);
void FrontBackSplit(Node* source, Node** frontRef, Node** backRef);
void MergeSort(Node** headRef) {
Node* head = *headRef;
Node* a, *b;
if ((head == NULL) || (head->arbit == NULL))
return;
FrontBackSplit(head, &a, &b);
MergeSort(&a);
MergeSort(&b);
*headRef = SortedMerge(a, b);
}
Node* SortedMerge(Node* a, Node* b) {
Node* result = NULL;
if (a == NULL)
return (b);
else if (b == NULL)
return (a);
if (a->data <= b->data){
result = a;
result->arbit = SortedMerge(a->arbit, b);
} else {
result = b;
result->arbit = SortedMerge(a, b->arbit);
}
return (result);
}
void FrontBackSplit(Node* source, Node** frontRef, Node** backRef) {
Node* fast, *slow;
if (source == NULL || source->arbit == NULL){
*frontRef = source;
*backRef = NULL;
return;
}
slow = source, fast = source->arbit;
while (fast != NULL){
fast = fast->arbit;
if (fast != NULL){
slow = slow->arbit;
fast = fast->arbit;
}
}
*frontRef = source;
*backRef = slow->arbit;
slow->arbit = NULL;
}
void addNode(Node** head_ref, int new_data) {
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = (*head_ref);
new_node->arbit = NULL;
(*head_ref) = new_node;
}
Node* populateArbitraray(Node *head) {
Node *temp = head;
while (temp != NULL){
temp->arbit = temp->next;
temp = temp->next;
}
MergeSort(&head);
return head;
}
int main() {
Node* head = NULL;
addNode(&head, 45);
addNode(&head, 12);
addNode(&head, 87);
addNode(&head, 32);
Node *ahead = populateArbitraray(head);
cout << "\t\tArbitrary pointer overloaded \n Traversing linked List\n";
cout<<"Using Next Pointer\n";
while (head!=NULL){
cout << head->data << ", ";
head = head->next;
}
printf("\nUsing Arbit Pointer\n");
while (ahead!=NULL){
cout<<ahead->data<<", ";
ahead = ahead->arbit;
}
return 0;
}
실행 결과
Arbitrary pointer overloaded Traversing linked List Using Next Pointer 32, 87, 12, 45, Using Arbit Pointer 12, 32, 45, 87,
코드 동작 원리
- MergeSort() : 분할 정복 방식으로 리스트를 계속 반으로 나눈 뒤, 정렬된 결과를 다시 병합하는 재귀 함수입니다.
- FrontBackSplit() : slow/fast 두 포인터 기법을 사용해 리스트를 전반부와 후반부로 분할합니다.
- SortedMerge() : 두 개의 정렬된 리스트를 arbit 포인터 기준으로 하나로 병합합니다.
- populateArbitraray() : 처음에 arbit 포인터를 next 포인터와 동일하게 초기화한 후, 병합 정렬을 수행해 최종 리스트를 반환합니다.
실행 결과에서 확인할 수 있듯이, next 포인터로 순회하면 원래 입력 순서(32, 87, 12, 45)가 그대로 유지되는 반면, arbit 포인터로 순회하면 값이 오름차순(12, 32, 45, 87)으로 출력됩니다. 이는 각 노드의 임의 포인터가 성공적으로 '다음으로 큰 값'을 가진 노드를 가리키고 있음을 의미합니다.