View in English →

Code › algorithm-study

LeetCode 271 - Encode and Decode Strings

문자열 길이와 구분자를 함께 기록해 문자열 목록을 인코딩하고 복원하는 Python 풀이

algorithmleetcodestringencodingpythonlearning

이 문제는 문자열 목록을 하나의 문자열로 인코딩한 뒤, 원래 목록으로 정확히 복원하는 Medium 문제다. 문자열 사이에 구분자만 넣어서 인코딩 하면, 본문에 같은 문자가 포함됐을 때 디코딩 시 separator를 판단하기 어려워서, 각 문자열의 길이를 먼저 기록하는 방식으로 풀었다.

문제 링크 & 설명

  • 문제 링크: 271. Encode and Decode Strings
  • 요약: 문자열 목록을 하나의 문자열로 변환하는 encode 함수와, 인코딩된 문자열을 원래 목록으로 복원하는 decode 함수를 구현하는 문제.

예를 들어 다음 목록을 인코딩한다고 해보자.

["leet", "co%de", "", "soul"]

문자열 사이에 %만 넣으면 본문에 들어 있는 %와 목록을 나누는 %를 구분할 수 없다. 빈 문자열까지 포함되면 연속된 구분자가 빈 문자열을 뜻하는지, 데이터의 일부인지 판단하는 규칙도 추가로 필요하다.

이번 풀이에서는 각 문자열을 길이 + 구분자 + 본문 순서로 이어 붙였다.

4%leet5%co%de0%4%soul

접근 방법

encode에서는 문자열마다 길이를 먼저 적고, 길이 정보가 끝나는 위치에 %를 붙인 다음 본문을 이어 붙인다.

answer += f"{len(s)}%{s}"

여기서 %는 문자열 본문의 끝을 표시하지 않는다. 숫자로 된 길이 정보가 어디서 끝나는지만 알려 준다. 따라서 본문 안에 %가 들어 있어도 디코딩할 때 앞에서 읽은 길이만큼 본문을 가져오면 된다.

decode에서는 left와 right를 현재 길이 정보의 시작점에 둔다. right를 이동하며 %를 찾고, left부터 right 전까지의 숫자를 정수로 변환한다.

while s[right] != "%":
    right += 1

num_len = int(s[left:right])

구분자 다음 위치가 본문의 시작점이다. 이 위치부터 num_len만큼 잘라내면 문자열 하나를 정확히 복원할 수 있다.

start = right + 1
word = s[start : start + num_len]

문자열을 하나 복원한 뒤에는 그 본문이 끝난 위치로 left와 right를 함께 옮긴다. 다음 반복에서는 다시 길이 정보와 %를 찾는다.

left = start + num_len
right = left

트러블 슈팅

위에서 잠시 언급했던 것 처럼, 문자열 사이에 구분자만 넣고 split으로 나누면 입력 문자열에 같은 문자가 포함됐을 때 경계가 깨진다. 입력 문자열에는 어떤 문자든 들어올 수 있다고 본문에 쓰여져 있어서, 내가 선택한 구분자가 본문에 포함되지 않는다고 보장할 수 없다.

처음에는 구분자를 두 번 쓰거나 escape 규칙을 추가하면 어떨까? 하는 생각도 해보았지만, 이 방식은 인코딩과 디코딩 양쪽에서 예외 규칙을 계속 관리해야 하는 불편함이 있다. 그런데 문자열 길이를 함께 기록하는 방식으로 구현하게 되면 디코더는 본문의 내용을 해석하지 않고 정해진 길이만큼 바로 이동한다. 빈 문자열은 길이 0으로 기록되고, 본문에 %가 들어가더라도 길이만큼 읽은 뒤 다음 문자열의 시작점으로 바로 넘어간다.

네트워크 프로토콜과 파일 형식에서도 종료 문자, 길이 정보, 청크처럼 데이터의 경계를 전달하는 규칙이 필요하다. 이 부분은 문제 풀이와 분리해서 처음에 어떻게 이런 방법들이 고안되었는지까지 따로 정리하여 포스팅 할 예정!!

복잡도 분석

인코딩된 문자열의 전체 길이를 L이라고 하자.

  • 시간 복잡도

    • decode는 길이 정보와 각 본문을 순서대로 한 번씩 읽으므로 O(L)이다.
    • 현재 encode 구현은 immutable 문자열에 결과를 반복해서 이어 붙이므로, 매번 기존 문자열이 복사되는 최악의 경우 O(L²)까지 늘어날 수 있다. 조각을 list에 모은 뒤 join으로 합치면 O(L)로 처리할 수 있다.

  • 공간 복잡도: O(L)

    • encode는 인코딩된 결과 문자열을 만들고, decode는 복원한 문자열 목록을 저장한다.

구현 코드

class Solution:
    def encode(self, strs: list[str]) -> str:
        answer = ""
        for s in strs:
            answer += f"{len(s)}%{s}"
        return answer

    def decode(self, s: str) -> list[str]:
        left = 0
        right = 0
        str_len = len(s)

        result = []
        while right < str_len:
            while s[right] != "%":
                right += 1

            num_len = int(s[left:right])
            start = right + 1
            word = s[start : start + num_len]
            result.append(word)

            left = start + num_len
            right = left

        return result

입력 크기가 커지는 조건에서는 encode의 문자열 결합 방식도 함께 바꾸는 편이 안전하다. 반복할 때마다 완성된 문자열을 다시 만드는 대신, 각 문자열의 인코딩 결과를 list에 담은 뒤 마지막에 join으로 한 번만 합칠 수 있다.

def encode(self, strs: list[str]) -> str:
    parts = []

    for s in strs:
        parts.append(f"{len(s)}%{s}")

    return "".join(parts)

이렇게 하면 기존 결과를 반복해서 복사하지 않으므로 인코딩된 전체 문자열 길이 L에 대해 시간복잡도를 O(L)로 유지할 수 있다.

요약 및 회고

이번 문제는 풀면서 실제로 HTTP 프로토콜에서 사용되는 방식에 대한 알고리즘이 무엇인가 호기심도 생겼다. 그냥 무심코 사용하던 부분이지만 이렇게 알고리즘과 엮고, 또 다음에 포스팅할 인코딩 디코딩 관련 글이랑 지식이 합쳐져서 마치 시냅스가 연결되듯이 계속 활성화되게끔 하고 싶다. 아무튼 솔루션 자체는, 처음에는 떠올리지 못했지만 찾아보면서 공부하고 재미있게 풀었던 문제였다.