C++ 단일 연결 리스트에서 소수가 아닌 노드 모두 삭제하기

이 튜토리얼에서는 C++를 사용해 단일 연결 리스트(Singly Linked List)에서 소수(prime)가 아닌 노드를 모두 삭제하는 방법을 알아봅니다. 예제 코드와 함께 단계별로 차근차근 살펴보겠습니다.

문제 해결 접근 방식

문제를 해결하기 위한 전체적인 흐름은 다음과 같습니다.

데이터(data)와 다음 노드를 가리키는 포인터(next)를 가지는 구조체(struct)를 작성합니다.
단일 연결 리스트에 새 노드를 삽입하는 함수를 작성합니다.
테스트용 더미 데이터로 연결 리스트를 초기화합니다.
연결 리스트를 순회하면서 현재 노드의 데이터가 소수인지 판별합니다.
현재 데이터가 소수가 아니라면 해당 노드를 삭제합니다.

노드 삭제 시 고려할 세 가지 경우

노드를 삭제하는 함수를 작성할 때는 아래의 세 가지 상황을 반드시 고려해야 합니다.

헤드(head) 노드인 경우: 헤드 포인터를 다음 노드로 이동시킵니다.
중간 노드인 경우: 이전 노드와 다음 노드를 연결합니다.
마지막 노드인 경우: 이전 노드의 링크(next)를 제거합니다.

예제 코드

이제 실제 동작하는 C++ 코드를 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node* next;
};
void insertNode(Node** head_ref, int new_data) {
    Node* new_node = new Node;
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}
bool isPrime(int n) {
    if (n <= 1) {
        return false;
    }
    if (n <= 3) {
        return true;
    }
    if (n % 2 == 0 || n % 3 == 0) {
        return false;
    }
    for (int i = 5; i * i <= n; i = i + 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}
void deleteNonPrimeNodes(Node** head_ref) {
    Node* ptr = *head_ref;
    while (ptr != NULL && !isPrime(ptr->data)) {
        Node *temp = ptr;
        ptr = ptr->next;
        delete(temp);
    }
    *head_ref = ptr;
    if (ptr == NULL) {
        return;
    }
    Node *curr = ptr->next;
    while (curr != NULL) {
        if (!isPrime(curr->data)) {
            ptr->next = curr->next;
            delete(curr);
            curr = ptr->next;
        }
        else {
            ptr = curr;
            curr = curr->next;
        }
    }
}
void printLinkedList(Node* head) {
    while (head != NULL) {
        cout << head->data << " -> ";
        head = head->next;
    }
}
int main() {
    Node* head = NULL;
    insertNode(&head, 1);
    insertNode(&head, 2);
    insertNode(&head, 3);
    insertNode(&head, 4);
    insertNode(&head, 5);
    insertNode(&head, 6);
    cout << "Linked List before deletion:" << endl;
    printLinkedList(head);
    deleteNonPrimeNodes(&head);
    cout << "\nLinked List after deletion:" << endl;
    printLinkedList(head);
}

코드 설명

isPrime 함수는 소수 판별 알고리즘 중 하나인 6k±1 최적화 기법을 사용합니다. 2와 3의 배수를 먼저 걸러낸 후, √n까지의 수만 검사하므로 효율적입니다.

deleteNonPrimeNodes 함수는 두 단계로 동작합니다. 먼저 리스트 앞쪽의 소수가 아닌 노드들을 삭제하여 유효한 첫 번째 노드를 찾고, 이후에는 이전 노드(ptr)와 현재 노드(curr)를 추적하며 소수가 아닌 노드를 건너뛰도록 링크를 재조정합니다.

실행 결과

위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

Linked List before deletion:
6 -> 5 -> 4 -> 3 -> 2 -> 1 ->
Linked List after deletion:
5 -> 3 -> 2 ->

삽입 순서상 리스트는 역순으로 구성되므로 초기 리스트는 6 -> 5 -> 4 -> 3 -> 2 -> 1입니다. 여기서 소수가 아닌 값(6, 4, 1)이 제거되어 최종적으로 5 -> 3 -> 2만 남게 됩니다.

마무리

이번 튜토리얼에서는 단일 연결 리스트를 순회하며 소수 판별 함수를 활용해 조건에 맞는 노드를 안전하게 삭제하는 방법을 배웠습니다. 메모리 누수를 방지하기 위해 delete로 노드를 반드시 해제해 주는 것도 잊지 마세요. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요!