C++ 연결 리스트에서 모듈러 노드 찾기 – 개념부터 코드 구현까지

이 문제에서는 단일 연결 리스트(singly linked list) LL과 정수 k가 주어지며, 우리의 목표는 연결 리스트에서 모듈러 노드(modular node)를 찾는 것입니다.

문제 설명

모듈러 노드란 노드의 인덱스가 k로 나누어 떨어지는(즉, i % k == 0) 노드를 의미합니다. 이때 우리가 찾아야 하는 것은 해당 조건을 만족하는 노드 중 마지막(가장 뒤에 있는) 노드입니다.

예제로 문제 이해하기

입력

ll = 3 -> 1 -> 9 -> 6 -> 8 -> 2, k = 4

출력

6

설명

연결 리스트의 각 노드는 1부터 시작하는 인덱스를 가집니다. 여기서 요소 6은 인덱스 4에 위치하며, 4 % k == 0(k = 4)을 만족합니다. 이후 인덱스 5, 6의 노드는 조건을 만족하지 않으므로, 최종 답은 6이 됩니다.

해결 접근 방식

가장 간단한 해결 방법은 다음과 같습니다.

• 카운터 변수 i를 사용하여 연결 리스트를 순회하면서 각 노드의 위치를 셉니다.
• 순회 도중 i % k == 0 조건을 만족할 때마다 해당 노드를 결과 변수에 저장합니다.
• 조건을 만족하는 노드가 나올 때마다 계속 갱신하므로, 순회가 끝나면 자동으로 마지막 모듈러 노드가 저장됩니다.

이 방식은 리스트를 한 번만 순회하면 되기 때문에 시간 복잡도는 O(n), 추가 공간은 상수만 사용하므로 공간 복잡도는 O(1)입니다.

구현 예제

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};

Node* newNode(int data) {
    Node* new_node = new Node;
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}

Node* findModularNodeLL(Node* head, int k) {
    if (k <= 0 || head == NULL)
        return NULL;
    int i = 1;
    Node* modNode = NULL;
    for (Node* currNode = head; currNode != NULL; currNode = currNode->next) {
        if (i % k == 0)
            modNode = currNode;
        i++;
    }
    return modNode;
}

int main() {
    Node* head = newNode(3);
    head->next = newNode(1);
    head->next->next = newNode(9);
    head->next->next->next = newNode(6);
    head->next->next->next->next = newNode(8);
    head->next->next->next->next->next = newNode(2);

    int k = 4;
    Node* modularNode = findModularNodeLL(head, k);

    cout<<"연결 리스트의 모듈러 노드는 ";
    if (modularNode != NULL)
        cout<<modularNode->data;
    else
        cout<<"찾을 수 없습니다!";

    return 0;
}

출력

연결 리스트의 모듈러 노드는 6

코드 설명

• findModularNodeLL 함수: k가 0 이하이거나 리스트가 비어 있으면 NULL을 반환하여 예외 상황을 먼저 처리합니다.
• 인덱스 i는 1부터 시작하며, 순회 중 i % k == 0을 만족하는 노드를 modNode에 계속 갱신합니다.
• 순회가 종료되면 modNode에는 조건을 만족하는 마지막 노드가 저장되어 반환됩니다.

이처럼 한 번의 순회만으로 원하는 노드를 효율적으로 찾을 수 있으며, 연결 리스트 관련 기초 알고리즘 문제를 학습하기에 좋은 예제입니다.