Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

연결 리스트에서 K번째 노드마다 삭제하는 방법

이 글에서는 연결 리스트(Linked List)에서 k번째에 해당하는 모든 노드를 제거하는 방법을 알아보겠습니다. 즉, k, 2k, 3k... 처럼 k의 배수 위치에 있는 노드들을 모두 삭제해야 합니다.

문제 이해하기

먼저 입력과 출력 예시를 통해 문제를 명확히 파악해 보겠습니다.

입력 : 112->231->31->41->54->63->71->85
k = 3
출력 : 112->231->41->54->71->85

위 예시에서는 k가 3이므로 3번째 노드(31), 그다음으로 41부터 다시 세어 3번째인 노드(63)를 순차적으로 삭제합니다. 두 번째 반복 후 리스트는 112->231->41->54->71->85가 되며, 같은 방식으로 끝까지 진행됩니다.

입력 : 14->21->23->54->56->61
k = 1
출력 : 빈 리스트

k가 1이면 모든 노드가 삭제 대상이 되므로 결과적으로 빈 리스트가 됩니다.

해결 접근 방법

이 문제는 별도의 최적화 없이도 충분히 효율적인 일반적인 순회 방식으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  • 연결 리스트를 순회하면서 카운터(counter)를 사용해 현재 위치를 추적합니다.
  • 카운터가 k에 도달하면 해당 노드를 삭제하고, 카운터를 1로 초기화하여 다음 k번째 위치를 찾기 시작합니다.
  • 현재 포인터(current)와 이전 포인터(prev)를 함께 관리해야 노드 삭제 시 연결 관계를 올바르게 유지할 수 있습니다.

C++ 구현 예제

#include<bits/stdc++.h>
using namespace std;
/* 연결 리스트 노드 구조체 */
struct Node {
    int data;
    struct Node* next;
};
void push(struct Node** ref, int new_data) { // 리스트에 데이터 삽입
    struct Node* new_n = new Node;
    new_n->data = new_data;
    new_n->next = (*ref);
    (*ref) = new_n;
}
void deletek(Node* prev, Node* curr) { // 노드 삭제 함수
    if(prev == NULL) {
        prev = curr;
        curr = curr -> next;
        free(prev);
        prev = NULL;
    } else {
        prev -> next = curr -> next;
        auto tmp = curr;
        free(tmp); // 메모리 해제
    }
}
/* 연결 리스트 출력 함수 */
void displayList(struct Node *head) {
    struct Node *temp = head;
    while (temp != NULL) {
        cout<<temp->data<<" ";
        temp = temp->next;
    }
}
// 새 노드 생성 함수
struct Node *newNode(int x) {
    Node *temp = new Node;
    temp->data = x;
    temp->next = NULL;
    return temp;
}
int main() {
    struct Node* head = NULL;
    push(&head, 80);
    push(&head, 70);
    push(&head, 60);
    push(&head, 50);
    push(&head, 40);
    push(&head, 30);
    push(&head, 20);
    int k = 3; // 주어진 k 값
    Node* curr = head; // 현재 포인터
    Node* prev = NULL; // 이전 포인터
    int count = 1; // 위치 카운터
    if(head == NULL || k == 0) // 리스트가 비어 있거나 k = 0인 경우
        cout << "Invalid\n";
    else {
        while(curr) { // 리스트 순회
            if(count == k) {
                deletek(prev, curr);
                curr = prev -> next;
                count = 1;
            } else {
                count++;
                prev = curr;
                curr = curr -> next;
            }
        }
        displayList(head); // 새 리스트 출력
    }
    return 0;
}

실행 결과

20 30 50 60 80

원래 리스트는 20->30->40->50->60->70->80이었고, k = 3이므로 3번째 노드(40)와 6번째 노드(70)가 삭제되어 위와 같은 결과가 출력됩니다.

코드 동작 원리 상세 설명

이 알고리즘은 세 가지 요소를 유지하면서 동작합니다. 첫째, 현재 포인터(curr), 둘째, 이전 포인터(prev), 셋째, 위치 카운터(count)입니다.

  1. 리스트를 순회하다가 카운터가 k와 같아지면, 이전 포인터와 현재 포인터를 인자로 전달하며 삭제 함수를 호출합니다.
  2. 삭제 함수는 현재 노드의 메모리를 해제(free)하고, 이전 노드의 next 포인터를 현재 노드의 다음 노드로 연결하여 리스트의 연속성을 유지합니다.
  3. 삭제가 완료되면 현재 포인터를 다음 노드로 이동시키고, 카운터를 1로 초기화한 뒤 같은 과정을 반복합니다.
  4. 현재 포인터가 NULL이 되면 순회를 종료하고 새로운 리스트를 출력합니다.

이 접근 방식의 시간 복잡도는 O(N)입니다. 여기서 N은 주어진 연결 리스트의 크기를 의미하며, 각 노드를 한 번씩만 방문하므로 매우 효율적입니다.

마무리

이번 글에서는 연결 리스트에서 k번째 노드마다 삭제하는 문제를 해결해 보았습니다. 일반적인 순회 기반 접근 방식과 이를 구현한 C++ 프로그램을 함께 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 작성할 수 있습니다. 이 글이 여러분의 학습에 도움이 되기를 바랍니다.