Python으로 런 길이 인코딩(RLE) 문자열을 원래 형태로 디코딩하는 방법

문자열 s가 있다고 가정해 보겠습니다. s는 런 길이 인코딩(run-length encoding) 방식으로 압축된 문자열이며, 우리는 이를 다시 원래의 문자열로 복원(디코딩)해야 합니다.

런 길이 인코딩(RLE)은 문자열을 빠르고 간단하게 압축하는 대표적인 기법입니다. 기본 아이디어는 연속해서 반복되는 문자들을 하나의 개수(count)와 문자(character) 쌍으로 표현하는 것입니다. 예를 들어 "BBBBAAADDCBB"라는 문자열은 "4B3A2D1C2B"로 인코딩됩니다.

따라서 입력이 s = "4B3A2D1C2B"라면 출력은 "BBBBAAADDCBB"가 되어야 합니다.

풀이 접근 방식

이 문제는 다음 단계를 따라 해결할 수 있습니다.

결과를 담을 빈 문자열 output과, 숫자 부분을 임시로 저장할 빈 문자열 num을 준비합니다.
s의 각 문자 i를 차례대로 확인하며 다음을 수행합니다.
- i가 알파벳인 경우: output에 i를 num을 정수로 변환한 값만큼 반복해 추가한 뒤, num을 다시 빈 문자열로 초기화합니다.
- i가 숫자인 경우: num에 i를 이어 붙입니다. 덕분에 10 이상의 두 자리 반복 횟수도 올바르게 처리할 수 있습니다.
모든 문자를 확인한 후 output을 반환합니다.

구현 예제

class Solution:
    def solve(self, s):
        output = ""
        num = ""
        for i in s:
            if i.isalpha():
                output += i * int(num)
                num = ""
            else:
                num += i
        return output

ob = Solution()
print(ob.solve("4B3A2D1C2B"))

입력 및 실행 결과

입력: "4B3A2D1C2B"

출력:

BBBBAAADDCBB

코드 동작 원리

이 코드의 핵심은 두 가지입니다. 첫째, isalpha() 메서드로 현재 문자가 알파벳인지 판별합니다. 둘째, 파이썬의 문자열 반복 연산자(*)를 활용해 해당 문자를 지정된 횟수만큼 손쉽게 확장합니다. 숫자를 한 글자씩 모아 두었다가 알파벳을 만나는 시점에 한 번에 정수로 변환하기 때문에, "12A"처럼 두 자리 이상의 반복 횟수도 문제없이 처리됩니다.

시간 및 공간 복잡도

인코딩된 문자열의 길이를 n, 디코딩된 최종 문자열의 길이를 N이라 하면 시간 복잡도는 O(n + N), 공간 복잡도는 O(N)입니다. 즉, 최종 출력 크기에 비례하는 선형 시간에 동작하는 효율적인 알고리즘입니다. 참고로 매우 긴 문자열을 다룰 때는 문자열 조각을 리스트에 모은 뒤 ''.join()으로 합치는 방식이 반복적인 += 연산보다 더 나은 성능을 보일 수 있습니다.