C++ 연결 리스트로 런 길이 인코딩(RLE) 구현하기

이번 튜토리얼에서는 연결 리스트(Linked List)를 활용해 런 길이 인코딩(Run Length Encoding, RLE)을 구현하는 C++ 프로그램을 살펴보겠습니다.

런 길이 인코딩(RLE)이란?

런 길이 인코딩은 연속해서 반복되는 데이터를 '값 + 반복 횟수' 형태로 치환하는 대표적인 무손실 압축 기법입니다. 이번 예제의 목표는 주어진 연결 리스트의 요소들을 이 방식으로 인코딩하는 것입니다.

예를 들어 연결 리스트의 요소가 "a->a->a->a->a"라면, 런 길이 인코딩을 적용한 결과는 "a → 5"가 됩니다. 즉, 문자 'a'가 5번 연속으로 나타난다는 의미입니다.

C++ 구현 예제

아래 코드는 노드 구조체 정의, 새 노드 생성, 노드 추가, 리스트 출력, 그리고 실제 인코딩을 수행하는 함수까지 전체 과정을 담고 있습니다. 입력 리스트가 "a → a → b → b → r → r"이라면 각 문자가 2번씩 반복되므로 최종적으로 "a 2 b 2 r 2"가 출력됩니다.

#include <bits/stdc++.h>
using namespace std;
// 연결 리스트 노드 구조체 정의
struct Node {
    char data;
    struct Node* next;
};
// 새 노드 생성
Node* newNode(char data){
    Node* temp = new Node;
    temp->data = data;
    temp->next = NULL;
    return temp;
}
// 리스트 끝에 노드 추가
void add_node(struct Node* head_ref, char new_data){
    struct Node* new_node = newNode(new_data);
    struct Node* last = head_ref;
    if (head_ref == NULL) {
        head_ref = new_node;
        return;
    }
    while (last->next != NULL)
        last = last->next;
    last->next = new_node;
    return;
}
// 연결 리스트 출력
void print_llist(Node* node){
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
}
// 주어진 리스트를 런 길이 인코딩
void llist_encode(Node* head){
    Node* p = head;
    Node* temp = newNode(p->data);
    char c = p->data;
    p = p->next;
    int count = 1;
    while (p != NULL) {
        char x = p->data;
        if (c == x)
            count++;
        else {
            if (count > 1) {
                if (count > 9)
                    add_node(temp, '0' + (count / 10));
                add_node(temp, '0' + (count % 10));
            }
            count = 1;
            add_node(temp, x);
            c = x;
        }
        p = p->next;
    }
    if (count != 0)
        add_node(temp, '0' + count);
    print_llist(temp);
}
int main(){
    Node* head = newNode('a');
    head->next = newNode('a');
    head->next->next = newNode('b');
    head->next->next->next = newNode('b');
    head->next->next->next->next = newNode('r');
    head->next->next->next->next->next = newNode('r');
    llist_encode(head);
    return 0;
}

코드 동작 원리

llist_encode() 함수는 리스트를 한 번만 순회하면서 현재 문자와 다음 문자를 비교합니다. 같은 문자가 이어지면 카운트를 1씩 증가시키고, 다른 문자가 등장하면 그동안 세었던 카운트를 임시 리스트에 추가한 뒤 기준 문자를 새로 바꿉니다. 특히 반복 횟수가 9를 초과할 경우 '0' + (count / 10)과 '0' + (count % 10)으로 자릿수를 나누어 두 개의 숫자 노드로 저장하기 때문에, 두 자리 수 반복 횟수도 올바르게 처리할 수 있다는 점이 특징입니다.

실행 결과

a 2 b 2 r 2

'a', 'b', 'r'이 각각 2번씩 연속 등장했기 때문에 위와 같은 결과가 출력됩니다. 이처럼 런 길이 인코딩은 반복 패턴이 많은 데이터에서 저장 공간을 크게 절약할 수 있는 효율적인 압축 방식입니다.