Day 58: 파이썬 Run-Length Encoding (RLE) – 초간단 O(n) 트릭으로 문자열을 전문가처럼 압축하기
Source: Dev.to
Introduction
#80DaysOfChallenges 여정의 Day 58에 오신 것을 환영합니다! 이번 중급 챌린지는 Run-Length Encoding (RLE), 즉 "AAAAABBBCC"를 "A5B3C2"로 바꾸는 고전 압축 기법을 구현합니다. 팩스 기계, BMP 이미지, 일부 게임 포맷에서도 사용되는 동일한 방법이며, 반복 문자가 긴 데이터에 대해 놀라울 정도로 효과적입니다.
해답은 순수하고 가독성이 좋으며 O(n) 시간에 O(1) 추가 공간(출력 제외)으로 동작합니다. 라이브러리 없이, 복잡함 없이, 깔끔한 파이썬 코드만으로 구현되었습니다.
압축, 데이터 인코딩에 관심이 있거나 긴 문자열이 눈에 띄게 줄어드는 모습을 보고 싶다면, 이 “Python RLE compressor”는 아름답고 실용적이며 즉시 활용할 수 있습니다.
Example
"WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWB"
→ "W12B1W12B3W24B1"Key Takeaways from Day 58: RLE Encoder Function
Function Design: Immediate Empty Check
def rle_encode(text: str) -> str:
if not text:
return ""
result = []
count = 1입력이 비어 있을 경우 빈 문자열을 반환합니다. 효율적인 문자열 구축을 위한 result 리스트와 count = 1(단일 문자는 길이 1) 초기화가 이루어집니다.
Core Loop: Run Detection Magic
for i in range(1, len(text)):
if text[i] == text[i - 1]:
count += 1
else:
result.append(f"{text[i - 1]}{count}")
count = 1- 현재 문자가 이전 문자와 같다면
count를 증가시킵니다. - 다르면 현재 구간을 닫고
result에 추가한 뒤,count = 1로 새로운 구간을 시작합니다.
예를 들어 "AAA"일 경우:
i = 1 → count = 2, i = 2 → count = 3 → 루프 종료 → 마지막에 "A3"을 추가합니다.
Final Run: Never Forget the Last Group!
# Handle the final run
result.append(f"{text[-1]}{count}")
return "".join(result)루프가 마지막 구간을 놓치기 때문에, 종료 시 반드시 한 번 더 추가해 줍니다. 이는 구간 기반 알고리즘에서 흔히 쓰이는 패턴입니다.
Main Interactive: Real Testing
user_input = input("Enter a string to encode: ").strip()
if user_input == "":
print("No input provided. Exiting.")
else:
encoded = rle_encode(user_input)
print(f"Encoded (RLE): {encoded}")입력을 깔끔히 받고 즉시 압축 결과를 출력합니다. "aaaabbbcca"를 입력하면 "a4b3c2a1"이 출력됩니다.
Summary and Reflections
이 RLE 인코더는 짧고 완벽하며 데이터 압축에서 가장 유용한 패턴 중 하나인 구간 탐지 + 카운터 초기화를 보여줍니다. 주요 교훈은 다음과 같습니다:
- 마지막 구간을 별도로 처리해야 함 – 모든 런‑길이 알고리즘에서 공통.
list + join이+=보다 빠름 – 긴 구간에서는 O(n) vs. O(n²).- 실제 압축 파워 –
"A"× 1 000 000을"A1000000"으로 압축하면 매우 작아집니다!
이 기법은 PNG, TIFF, 일부 비디오 코덱에서도 사용됩니다.
Advanced Alternatives
- 디코드 함수 구현 (RLE는 가역적!).
- 입력에 숫자가 포함된 경우 처리 (현재 버전은
"111"을 세 개의'1'문자로 간주). - 파일 압축을 위한 바이너리 RLE 적용.
Next Steps and Resources
Day 58을 통해 몇 줄만으로 실제 압축 능력을 얻었습니다. 이름을 1000번 반복해서 압축해 보세요!
- Challenge #58 소스 코드: scripts/run_length_encoding.py
- 메인 레포지토리: 80-days-of-challenges
- 일일 업데이트: Twitter/X (@Shahrouzlogs)
가장 길게 압축한 구간은 무엇인가요? 아래에 가장 대단한 문자열을 남겨 주세요! 🔥