[알고리즘][문자열] 압축 및 해제 예제

📌 문자열 압축 & 해제 개요

개념 설명

압축	연속된 문자를 문자+개수 형식으로 표현 (예: "aaabbc" → "a3b2c1")
해제(복원)	압축된 문자열을 다시 원래 문자열로 복원 (예: "a3b2c1" → "aaabbc")

---

📘 1. 문자열 압축 개념 정리

✅ 압축 규칙

• 연속된 문자를 찾아 개수를 셈
• [문자][개수] 형태로 저장
• 예: "aabcccccaaa" → "a2b1c5a3"

✅ 압축 예시

원본 압축 결과

"aaaabb"	"a4b2"
"abcd"	"a1b1c1d1"
"aabcc"	"a2b1c2"

---

📗 2. 문자열 해제 개념 정리

✅ 해제 규칙

• 압축된 문자열에서 문자 뒤 숫자만큼 반복
• [문자][개수] → 문자 × 개수
• 예: "a3b2c1" → "aaabbc"

✅ 해제 예시

압축 해제 결과

"a4b2"	"aaaabb"
"a1b1c1d1"	"abcd"
"a2b1c2"	"aabcc"

---

🔧 3. 자바(Java) 구현

🔹 문자열 압축

public String compress(String str) {
    if (str == null || str.isEmpty()) return str;
    StringBuilder sb = new StringBuilder();
    int count = 1;
    for (int i = 0; i < str.length(); i++) {
        if (i + 1 < str.length() && str.charAt(i) == str.charAt(i + 1)) {
            count++;
        } else {
            sb.append(str.charAt(i)).append(count);
            count = 1;
        }
    }
    return sb.toString();
}

🔹 문자열 해제

public String decompress(String compressed) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < compressed.length(); i++) {
        char ch = compressed.charAt(i);
        i++;
        StringBuilder num = new StringBuilder();
        while (i < compressed.length() && Character.isDigit(compressed.charAt(i))) {
            num.append(compressed.charAt(i++));
        }
        i--; // 숫자 다 읽었으면 한 칸 뒤로
        int count = Integer.parseInt(num.toString());
        for (int j = 0; j < count; j++) {
            sb.append(ch);
        }
    }
    return sb.toString();
}

 

---

🔧 4. C 언어 구현

🔹 문자열 압축

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* compress(const char* str) {
    int len = strlen(str);
    char* result = malloc(len * 2 + 1); // worst case
    int idx = 0;
    for (int i = 0; i < len;) {
        char current = str[i];
        int count = 1;
        while (i + 1 < len && str[i] == str[i + 1]) {
            count++;
            i++;
        }
        result[idx++] = current;
        idx += sprintf(result + idx, "%d", count);
        i++;
    }
    result[idx] = '\0';
    return result;
}

🔹 문자열 해제

char* decompress(const char* compressed) {
    int len = strlen(compressed);
    char* result = malloc(len * 10); // 충분한 크기 확보
    int idx = 0;
    for (int i = 0; i < len;) {
        char ch = compressed[i++];
        int count = 0;
        while (i < len && isdigit(compressed[i])) {
            count = count * 10 + (compressed[i++] - '0');
        }
        for (int j = 0; j < count; j++) {
            result[idx++] = ch;
        }
    }
    result[idx] = '\0';
    return result;
}

 

---

🔧 5. 파이썬(Python) 구현

🔹 문자열 압축

def compress(s):
    if not s:
        return s
    result = []
    count = 1
    for i in range(len(s)):
        if i + 1 < len(s) and s[i] == s[i+1]:
            count += 1
        else:
            result.append(s[i] + str(count))
            count = 1
    return ''.join(result)

🔹 문자열 해제

def decompress(compressed):
    result = []
    i = 0
    while i < len(compressed):
        ch = compressed[i]
        i += 1
        count = ''
        while i < len(compressed) and compressed[i].isdigit():
            count += compressed[i]
            i += 1
        result.append(ch * int(count))
    return ''.join(result)

 

---

📌 요약 정리

항목 설명

문제 목적	연속된 문자 압축/복원
압축 형식	[문자][개수] 반복
적용 예시	"aaabbcccc" → "a3b2c4"
활용	로그 저장, 데이터 전송 최적화 등
주의점	개수가 1인 경우도 포함함 (a1)