개요
이 튜토리얼에서는 주어진 두 개의 연결 리스트(Linked List)로부터 새로운 연결 리스트를 생성하는 C++ 프로그램을 작성해 보겠습니다.
크기가 같은 두 개의 연결 리스트가 주어졌을 때, 각 위치에서 두 노드의 값 중 더 큰 값을 선택하여 새로운 연결 리스트를 만드는 것이 목표입니다.
문제 해결 접근 방식
문제를 해결하는 단계는 다음과 같습니다.
- 노드 구조체(struct Node)를 정의합니다.
- 크기가 같은 두 개의 연결 리스트를 생성합니다.
- 두 연결 리스트를 동시에 순회합니다.
- 각 위치에서 두 노드 중 최대값을 찾습니다.
- 최대값을 데이터로 가지는 새 노드를 생성합니다.
- 새 노드를 결과 연결 리스트에 추가합니다.
- 새로 만들어진 연결 리스트를 출력합니다.
예제 코드
그럼 전체 코드를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* next;
};
void insertNewNode(Node** root, int item) {
Node *ptr, *temp;
temp = new Node;
temp->data = item;
temp->next = NULL;
if (*root == NULL) {
*root = temp;
}
else {
ptr = *root;
while (ptr->next != NULL) {
ptr = ptr->next;
}
ptr->next = temp;
}
}
void printLinkedList(Node* root) {
while (root != NULL) {
cout << root->data << " -> ";
root = root->next;
}
cout << "NULL" << endl;
}
Node* generateNewLinkedList(Node* root1, Node* root2) {
Node *ptr1 = root1, *ptr2 = root2;
Node* root = NULL;
while (ptr1 != NULL) {
int currentMax = ((ptr1->data < ptr2->data) ? ptr2->data : ptr1->data);
if (root == NULL) {
Node* temp = new Node;
temp->data = currentMax;
temp->next = NULL;
root = temp;
}
else {
insertNewNode(&root, currentMax);
}
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
return root;
}
int main() {
Node *root1 = NULL, *root2 = NULL, *root = NULL;
insertNewNode(&root1, 1);
insertNewNode(&root1, 2);
insertNewNode(&root1, 3);
insertNewNode(&root1, 4);
insertNewNode(&root2, 3);
insertNewNode(&root2, 1);
insertNewNode(&root2, 2);
insertNewNode(&root2, 4);
root = generateNewLinkedList(root1, root2);
printLinkedList(root);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
3 -> 2 -> 3 -> 4 -> NULL
시간 복잡도 분석
두 연결 리스트를 동시에 한 번씩 순회하므로 기본 순회 자체는 O(N)입니다. 다만 위 코드의 insertNewNode 함수는 노드를 추가할 때마다 리스트의 끝까지 탐색해야 하므로, 전체 시간 복잡도는 O(N²)이 됩니다.
이를 개선하려면 리스트의 마지막 노드를 가리키는 꼬리 포인터(tail pointer)를 유지하면 됩니다. 꼬리 포인터를 사용하면 노드 삽입이 O(1)에 이루어지므로 전체 알고리즘을 O(N)으로 최적화할 수 있습니다.
마무리
이 튜토리얼을 통해 두 연결 리스트의 각 위치에서 최대값을 비교하여 새로운 연결 리스트를 만드는 방법을 알아보았습니다. 내용에 대해 궁금한 점이 있다면 댓글로 남겨주세요.