C++ 문자열 인코딩 및 디코딩 알고리즘 완벽 가이드

여러 개의 문자열로 이루어진 리스트가 있다고 가정해 봅시다. 우리는 이 문자열 리스트를 하나의 문자열로 변환하는 인코더(encode)와, 인코딩된 문자열을 다시 원래의 리스트로 복원하는 디코더(decode)를 설계해야 합니다.

서로 다른 두 대의 머신에 각각 다음과 같은 함수가 설치되어 있다고 생각하면 이해하기 쉽습니다.

머신 1 (송신자)의 함수

string encode(vector<string> strs) {
    // 문자열들을 읽어 인코딩된 문자열(encoded_string)을 반환하는 코드;
}

머신 2 (수신자)의 함수

vector<string> decode(string s) {
    // 인코딩된 문자열을 디코딩하여 strs를 반환하는 코드;
}

동작 예시

입력이 {"hello", "world", "coding", "challenge"}라면, 인코딩 결과는 5#hello5#world6#coding9#challenge가 되며, 이를 다시 디코딩하면 [hello, world, coding, challenge] 형태의 원래 리스트를 얻게 됩니다.

핵심 아이디어: 길이 접두사 + 구분자 방식

이 문제의 핵심은 각 문자열 앞에 문자열의 길이와 # 구분자를 붙이는 것입니다. 이렇게 하면 문자열 내부에 '#'이나 숫자가 포함되어 있어도 길이 정보를 기준으로 정확하게 경계를 판단할 수 있으므로 안전하게 복원할 수 있습니다.

알고리즘 단계별 풀이

• encode() 함수 정의: 문자열 배열 strs를 입력으로 받습니다.

• 빈 문자열 ret을 초기화합니다.

• i = 0부터 strs의 크기까지 반복하면서 다음을 수행합니다.

  • ret에 strs[i]의 길이, '#', 그리고 strs[i] 자체를 차례대로 이어 붙입니다.

• 완성된 ret을 반환합니다.

• getNext() 함수 정의: 찾을 문자 x, 탐색 시작 위치 start, 대상 문자열 s를 받습니다.

• idx를 s의 크기로 초기화한 후, start 위치부터 끝까지 탐색하며 s[i]가 x와 같으면 idx에 i를 저장하고 반복을 종료합니다.

• idx를 반환합니다.

• decode() 함수 정의: 인코딩된 문자열 s를 입력으로 받습니다.

• 결과를 저장할 배열 ret과 위치 변수 i(0), 전체 길이 n(s의 크기)을 준비합니다.

• i < n인 동안 다음을 반복합니다.

  • getNext('#', i, s)로 현재 위치 이후의 첫 번째 '#' 위치(hashPos)를 찾습니다.

  • s의 i부터 hashPos 직전까지의 부분 문자열을 정수로 변환해 문자열 길이 len을 얻습니다.

  • i를 hashPos + 1로 옮긴 뒤, 해당 위치에서 len 길이만큼의 부분 문자열을 ret에 추가합니다.

  • i에 len을 더해 다음 문자열의 시작 위치로 이동합니다.

• 모든 문자열이 복원된 ret을 반환합니다.

C++ 구현 예제

아래 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i < v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]" << endl;
}

class Codec {
public:
    string encode(vector<string>& strs) {
        string ret = "";
        for (int i = 0; i < strs.size(); i++) {
            ret += to_string(strs[i].size()) + "#" + strs[i];
        }
        return ret;
    }

    int getNext(char x, int start, string s){
        int idx = s.size();
        for (int i = start; i < s.size(); i++) {
            if (s[i] == x) {
                idx = i;
                break;
            }
        }
        return idx;
    }

    vector<string> decode(string s) {
        vector<string> ret;
        int i = 0;
        int n = s.size();
        while (i < n) {
            int hashPos = getNext('#', i, s);
            int len = stoi(s.substr(i, hashPos - i));
            i = hashPos + 1;
            ret.push_back(s.substr(i, len));
            i += len;
        }
        return ret;
    }
};

main(){
    Codec ob;
    vector<string> v = {"hello", "world", "coding", "challenge"};
    string enc = (ob.encode(v));
    cout << "Encoded String " << enc << endl;
    print_vector(ob.decode(enc));
}

입력

{"hello", "world", "coding", "challenge"}

출력

Encoded String 5#hello5#world6#coding9#challenge
[hello, world, coding, challenge]

마무리

이 방식은 시간 복잡도 측면에서 인코딩과 디코딩 모두 전체 데이터 크기에 비례하는 O(N)으로 매우 효율적입니다. 또한 길이 접두사를 사용하기 때문에 문자열에 어떤 문자가 포함되어 있더라도 손실 없이 원본을 그대로 복원할 수 있다는 장점이 있습니다. 코딩 테스트나 시스템 설계 면접에서 자주 등장하는 유형이므로, 위 구현 과정을 직접 따라 작성해 보며 익혀두는 것을 추천합니다.