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

C++ 재귀 알고리즘으로 크기 k 그룹 단위 이중 연결 리스트 반전하기

이 문제에서는 이중 연결 리스트의 head 포인터와 정수 k가 주어지며, 리스트를 크기 k씩 묶인 그룹 단위로 반전해야 합니다. 예를 들어 다음과 같습니다.

입력 : 1 <-> 2 <-> 3 <-> 4 <-> 5 (이중 연결 리스트), k = 3
출력 : 3 <-> 2 <-> 1 <-> 5 <-> 4

위 예시에서 앞의 3개 노드(1, 2, 3)가 하나의 그룹으로 반전되고, 남은 노드(4, 5)도 하나의 그룹으로 반전되는 것을 확인할 수 있습니다.

문제 해결 접근 방법

이 문제는 재귀(recursion)를 활용한 알고리즘으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  • 리스트를 순회하면서 k개의 노드를 만날 때까지 각 노드의 next와 prev 포인터를 서로 교환하여 그룹 내부를 반전시킵니다.
  • k개의 노드를 모두 처리했다면, 현재 위치부터 시작하는 나머지 리스트에 대해 재귀 호출을 수행합니다.
  • 재귀 호출이 반환하는 새로운 head를 현재 그룹의 마지막 노드(반전 후에는 첫 번째 노드가 됨)의 next에 연결하여 그룹들을 이어줍니다.

C++ 구현 예제

#include <iostream>
using namespace std;

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

// 리스트 끝에 새 노드를 추가하는 push 함수
Node* push(Node* head, int data) {
    Node* new_node = new Node();
    new_node->data = data;
    new_node->next = NULL;
    Node* TMP = head;
    if (head == NULL) {
        new_node->prev = NULL;
        head = new_node;
        return head;
    }
    while (TMP->next != NULL) { // 마지막 노드까지 이동
        TMP = TMP->next;
    }
    TMP->next = new_node;
    new_node->prev = TMP;
    return head; // head 포인터 반환
}

// 주어진 리스트를 출력하는 함수
void printDLL(Node* head) {
    while (head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

// 크기 k 그룹 단위로 리스트를 반전하는 함수
Node* revK(Node* head, int k) {
    if (!head)
        return NULL;
    head->prev = NULL;
    Node *TMP, *CURRENT = head, *newHead;
    int count = 0;
    // count가 k보다 작은 동안 노드를 반전시킴
    while (CURRENT != NULL && count < k) {
        newHead = CURRENT;
        TMP = CURRENT->prev;
        CURRENT->prev = CURRENT->next;
        CURRENT->next = TMP;
        CURRENT = CURRENT->prev;
        count++;
    }
    if (count >= k) {
        // k개 이상 처리했다면 현재 head를 다음 그룹의 head에 연결
        head->next = revK(CURRENT, k);
    }
    return newHead;
}

int main() {
    Node* head = NULL;
    for (int i = 1; i <= 5; i++) {
        head = push(head, i);
    }
    cout << "원본 리스트 : ";
    printDLL(head);
    cout << "\n변경된 리스트 : ";
    int k = 3;
    head = revK(head, k);
    printDLL(head);
}

실행 결과

원본 리스트 : 1 2 3 4 5
변경된 리스트 : 3 2 1 5 4

코드 상세 설명

revK 함수는 리스트를 순회하면서 카운트가 k에 도달할 때까지 각 노드의 포인터를 교환하며 그룹 내부를 반전시킵니다. 여기서 중요한 점은 그룹 경계에서의 연결 처리입니다.

예를 들어 리스트가 1 2 3 4 5이고 k가 3이라면, 먼저 가운데 요소들이 반전되어 3 2 1이 됩니다. 하지만 이때 노드 1은 원래 2를 가리키다가 반전 과정에서 방향이 바뀌므로, 1이 다음 그룹의 첫 번째 요소인 4를 올바르게 가리키도록 연결을 다시 설정해야 합니다. 4 역시 이후에 반전될 대상이기 때문입니다.

이러한 이유로 재귀 호출을 사용하고, count >= k 조건문을 통해 현재 그룹의 마지막 노드(반전 전의 head)의 next를 다음 그룹의 반전 결과에 연결해 줍니다. 재귀 호출은 남은 노드가 없을 때까지 반복되며, 최종적으로 각 그룹이 순서대로 연결된 완성된 리스트가 반환됩니다.

마무리

이번 글에서는 재귀를 활용하여 이중 연결 리스트를 주어진 크기 k의 그룹 단위로 반전하는 문제를 해결해 보았습니다. C++로 작성된 전체 프로그램과 함께 단계별 접근 방법도 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다. 이 글이 여러분의 학습에 도움이 되기를 바랍니다.