C++ 연결 리스트에서 특정 정수의 등장 횟수 세기 – 반복문과 재귀로 구현

이 문제에서는 하나의 연결 리스트(Linked List)가 주어지며, 특정 정수가 이 리스트 안에서 몇 번 등장하는지 세어 그 횟수를 반환하는 함수를 작성해야 합니다.

먼저 예시를 통해 문제를 이해해 보겠습니다.

입력

연결 리스트 = 10 -> 50 -> 10 -> 20 -> 100 -> 10, 찾을 값 = 10

출력

3

설명 − 숫자 10이 연결 리스트 안에 총 3번 등장하기 때문입니다.

해결 아이디어

접근 방식은 매우 단순합니다. 연결 리스트를 첫 번째 노드부터 마지막 노드까지 순회(traverse)하면서, 현재 노드의 데이터 값이 찾고자 하는 값과 일치할 때마다 카운터를 1씩 증가시키면 됩니다. 순회가 끝난 뒤 카운터에 남아 있는 값이 곧 해당 숫자의 등장 횟수입니다.

노드를 순회하는 방식은 반복문(iteration)과 재귀 호출(recursion) 두 가지로 구현할 수 있으며, 이 글에서는 두 방법을 모두 다룹니다.

방법 1: 반복문으로 해결하기

포인터를 이용해 한 노드씩 이동하면서 조건을 검사하는 가장 일반적이고 안전한 방식입니다.

예제 코드

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
};

void push(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;
}

int countInt(Node* head, int search_for) {
    Node* current = head;
    int intCount = 0;
    while (current != NULL) {
        if (current->data == search_for)
            intCount++;
        current = current->next;
    }
    return intCount;
}

int main() {
    Node* head = NULL;
    push(&head, 10);
    push(&head, 40);
    push(&head, 10);
    push(&head, 50);
    push(&head, 20);
    push(&head, 90);
    push(&head, 10);

    cout << "연결 리스트에서 10의 개수는 " << countInt(head, 10);
    return 0;
}

출력

연결 리스트에서 10의 개수는 3

방법 2: 재귀로 해결하기

재귀를 활용하면 코드가 훨씬 간결해집니다. 현재 노드가 NULL이면 0을 반환하고, 그렇지 않으면 “현재 노드가 찾는 값과 일치하는지 여부(0 또는 1)”에 다음 노드의 재귀 호출 결과를 더하는 구조입니다. 전역 변수 없이 구현했기 때문에 함수가 독립적이고 재사용성과 스레드 안전성 면에서 유리합니다.

예제 코드

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
};

void push(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;
}

int countInt(Node* head, int key) {
    if (head == NULL)
        return 0;
    return (head->data == key ? 1 : 0) + countInt(head->next, key);
}

int main() {
    Node* head = NULL;
    push(&head, 10);
    push(&head, 40);
    push(&head, 10);
    push(&head, 50);
    push(&head, 20);
    push(&head, 90);
    push(&head, 10);

    cout << "연결 리스트에서 10의 개수는 " << countInt(head, 10);
    return 0;
}

출력

연결 리스트에서 10의 개수는 3

복잡도 분석

• 시간 복잡도: O(n) — 리스트의 모든 노드를 한 번씩 방문해야 합니다.
• 공간 복잡도: 반복문 방식은 O(1)이지만, 재귀 방식은 호출 스택이 쌓이므로 O(n)입니다.

따라서 리스트가 매우 길어질 가능성이 있다면 스택 오버플로 위험이 없는 반복문 방식을 사용하는 것이 더 안전합니다.