이 튜토리얼에서는 주어진 연결 리스트(Linked List)를 p:q 비율로 두 개의 리스트로 나누는 프로그램을 C++로 작성해 보겠습니다.
알고리즘 자체는 매우 간단합니다. 문제 해결 과정을 단계별로 살펴보겠습니다.
문제 해결 접근 방식
연결 리스트 노드를 위한 구조체(struct)를 정의합니다.
더미 데이터로 연결 리스트를 초기화합니다.
p:q 비율 값을 설정합니다.
연결 리스트의 전체 길이를 구합니다.
연결 리스트의 길이가 p + q보다 작으면 p:q 비율로 나누는 것이 불가능합니다.
나눌 수 있다면 p번째 노드까지 연결 리스트를 순회합니다.
p번째 노드 이후의 연결을 끊고, 두 번째 연결 리스트의 새로운 헤드(head)를 생성합니다.
마지막으로 분리된 두 연결 리스트를 출력합니다.
예제 코드
전체 코드를 살펴보겠습니다.
#include<bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *next;
Node(int data) {
this->data = data;
this->next = NULL;
}
};
void printLinkedList(Node* head) {
Node *temp = head;
while (temp) {
cout << temp->data << " -> ";
temp = temp->next;
}
cout << "NULL" << endl;
}
void splitLinkedList(Node *head, int p, int q) {
int n = 0;
Node *temp = head;
// 연결 리스트의 길이 구하기
while (temp != NULL) {
n += 1;
temp = temp->next;
}
// 연결 리스트를 나눌 수 있는지 확인
if (p + q > n) {
cout << "Can't divide Linked list" << endl;
}
else {
temp = head;
while (p > 1) {
temp = temp->next;
p -= 1;
}
// 분할 후 두 번째 연결 리스트의 헤드 노드
Node *head_two = temp->next;
temp->next = NULL;
// 연결 리스트 출력
printLinkedList(head);
printLinkedList(head_two);
}
}
int main() {
Node* head = new Node(1);
head->next = new Node(2);
head->next->next = new Node(3);
head->next->next->next = new Node(4);
head->next->next->next->next = new Node(5);
head->next->next->next->next->next = new Node(6);
int p = 2, q = 4;
splitLinkedList(head, p, q);
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
1 -> 2 -> NULL 3 -> 4 -> 5 -> 6 -> NULL
코드 동작 원리
위 예제에서는 노드가 6개인 연결 리스트를 p = 2, q = 4 조건으로 분할했습니다. 먼저 리스트를 순회하며 전체 길이(n = 6)를 구하고, p + q가 n보다 크지 않은지 확인합니다. 조건을 만족하면 첫 번째 노드부터 p번째 노드까지 이동한 뒤 해당 노드의 next 포인터를 NULL로 설정하여 연결을 끊습니다. 그 결과 앞의 2개 노드(1 → 2)와 뒤의 4개 노드(3 → 4 → 5 → 6), 즉 2:4 비율의 두 리스트가 만들어집니다.
이 알고리즘의 시간 복잡도는 O(n)이며, 추가적인 메모리를 사용하지 않으므로 공간 복잡도는 O(1)입니다.
마무리
이 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.