Python으로 문자열을 런 길이 인코딩(Run-Length Encoding)하는 방법

런 길이 인코딩(Run-Length Encoding)이란?

문자열 s가 주어졌을 때, 이를 런 길이 인코딩(Run-Length Encoding) 기법으로 압축하는 방법을 살펴보겠습니다. 런 길이 인코딩은 문자열을 빠르고 간단하게 압축할 수 있는 대표적인 방법으로, 핵심 아이디어는 연속해서 반복되는 문자들을 '개수 + 문자' 형태로 하나씩 묶어 표현하는 것입니다.

예를 들어 입력 문자열이 s = "BBBBAAADDCBB"라면 출력 결과는 "4B3A2D1C2B"가 됩니다. 이는 B가 4번, A가 3번, D가 2번, C가 1번, 그리고 B가 다시 2번 연속으로 나타났다는 의미입니다.

문제 해결 접근 방법

이 문제는 다음과 같은 단계로 해결할 수 있습니다.

• 결과를 저장할 빈 문자열 res를 초기화합니다.
• tmp에 문자열 s의 첫 번째 문자를 저장하고, count는 1로 설정합니다.
• 인덱스 1부터 문자열 끝까지 반복하며 다음을 수행합니다.
  • 현재 문자 s[i]가 tmp와 다르면, res에 count와 tmp를 이어 붙인 후 tmp를 새 문자로 갱신하고 count를 1로 초기화합니다.
  • 같은 문자라면 count를 1 증가시킵니다.
• 반복이 종료되면 마지막으로 남아 있는 count와 tmp를 res에 붙여 반환합니다.

Python 구현 코드

class Solution:
    def solve(self, s):
        res = ""
        tmp = s[0]
        count = 1
        for i in range(1, len(s)):
            if s[i] != tmp:
                res += str(count) + tmp
                tmp = s[i]
                count = 1
            else:
                count += 1
        return res + str(count) + tmp

ob = Solution()
print(ob.solve("BBBBAAADDCBB"))

입력

"BBBBAAADDCBB"

출력

4B3A2D1C2B

코드 동작 원리

위 코드는 문자열을 한 번만 순회하면서 이전 문자와 현재 문자를 비교합니다. 같은 문자가 계속 등장하면 카운트만 늘리고, 다른 문자가 나타나는 순간 지금까지 쌓인 카운트와 문자를 결과 문자열에 기록한 뒤 새로운 문자 기준으로 다시 카운트를 시작합니다. 마지막 문자 그룹은 반복문이 끝난 후 별도로 처리해야 누락되지 않습니다.

이 알고리즘의 시간 복잡도는 문자열 길이에 비례하는 O(n)으로 매우 효율적이며, 공간 복잡도 역시 결과 문자열 크기에 비례해 O(n)입니다. 반복 데이터가 많은 문자열일수록 압축 효율이 좋아진다는 점도 참고하면 유용합니다.