Encode and Decode Strings

gunny·2025년 12월 22일

Encode and Decode Strings NeetCode reetcode

coding_test

목록 보기

6/7

Encode and Decode Strings : https://neetcode.io/problems/string-encode-and-decode/question?list=neetcode150

문제 이해

문자열 직렬화(Serialization)과 역직렬화(Deserialization) 문제로 경계(Boundary)를 잃지 않고 여러 문자열을 하나로 합쳤다가 다시 복원하는 문제

문제 핵심

(1) Information Preservation 문제

정보를 손실 없이 변환했다가 복원할 수 있는가?

(2) Boundary Recognition 문제

문자열의 시작과 끝을 어떻게 알 것인가?

(3) Protocol Design 문제

송신자(encode)와 수신자(decode)가 같은 규칙(프로토콜)을 공유하고 있는가?

List<String> -> String -> List<String>
이 변환을 항상 역함수가 존재하도록 설계해야함.

즉, decode(encode(str)) == strs 가 항상 참이 되도록 만들어야함

이 문제는 문자열을 합치는 문제가 아니라 경계를 잃지 않는 데이터 인코딩 규칙을 설계하는 문제이다.

사고 흐름

사실 뭘 어떻게 풀어야하는 지 몰랐던 문제. 손도 못 댔음.

이 문제의 정석 패턴 이름은 관용적으로
Length-Prefixed Encoding (길이 접두 인코딩) 이라고 하는데
더 넓게는 Serialization / Deserialization, Message Framing, Self-describing Encoding

Length-Prefixed Encoding
: 데이터 앞에 '이 데이터의 길이'를 먼저 명시하는 방식
예 )
"neet" -> "4#neet"
"code" -> "4#coode"
이 패턴은 네트워크 프로토콜, 파일 포맷, OS/DB/Compiler 내부에서 수십 년간 쓰인 검증된 방식이다. 구분자 충도 없고, UTF-8 포함 문제 없고, 빈 문자열 문제 없고, 역변환이 항상 가능하다.

아무튼 이 문제에 접근하는 정석적인 사고 순서는
(1) 구분자를 쓰면 왜 안될까? 이다.
그 이유는 ':', '#', ',' 공백 등이 데이터 일 수 있으므로, 안 깨지는 구분자는 존재하지 않기 때문이다.

(2) 그렇다면 경계를 어떻게 알지?에 대한 흐름이다.
문자열의 끝을 알 수 있는 방법은
a. 특수문자를 이용
b. 길이를 미리 안다 이다.

특수문자는 '데이터' 이기도 하고. 메타 정보' 이기도 하기 때문에 불안정하다. 데이터의 일부일 수도 있기 때문에 이 이중적 의미(ambiguity)로 인해서 길이가 유일하게 안전한 boundary 가 된다.

(3) Decode가 어떻게 혼자서 복원가능하게 하지? 이다.
decode는 encode 로직을 '추측' 하면 안된다.
외부정보와 hidden state 없이 encode 규칙만으로 복원이 가능해야 한다.

(4) encode -> decode 는 역함수여야 한다.
반드시 여기서 성립해야하는 조건은

decode(encode(strs)) == strs

로 위 조건이 깨지면 설계 실패이다.

정석 풀이

그래서 Length-prifex로 정석 풀이를 해보면
Encode는 각 문자열 s에 대해 len(s)를 문자열로 붙이고, 구분자를 #로 한다. (예 : "neet" -> "4#neet")

Decode는 인덱스 i로 문자열을 순회해서
#을 만날 때까지 숫자를 읽고, 그 길이 만큼 substring을 반복한다.

class Solution:
    def encode(self, strs: List[str]) -> str:
        ans = []
        for s in strs:
            ans.append(str(len(s)))
            ans.append('#')
            ans.append(s)

        return ''.join(ans)


    def decode(self, s: str) -> List[str]:
        ans = []
        i = 0
        while i < len(s):
            j = i
            while s[j] != '#':
                j+=1
            
            length = int(s[i:j])

            start = j+1
            end = start + length
            ans.append(s[start:end])

            i = end

        return ans

decode에서 while 문으로 핸들링 했어야 했는데.. 구분자에 집착해서 풀지 못함. 각 문자열 s는 한번씩만 읽히므로 시간복잡도 O(n), 공간복잡도도 O(n)

추가

정석 풀이 법을 보기 전에 encode를 할때 ans = ''을 두고 +=을 사용해서 문자열 덧붙이기를 사용했는데, 문자열 덧붙이기는 python에서 비효율적이기 때문에 list에 누적한 뒤 join을 사용하는 것이 시간복잡도 O(n), 공간복잡도 O(n)을 보장하는 방법니다.
+=을 사용하면 누적 복사로 python 구현상 O(n^2) 가 될 수도있다.
-> 매 단계에서 기존 문자열을 전부 복사해서 그 뒤에 새 문자열을 붙이는 것으로 누적 비용이 폭증한다. **python에서 문자열은 immutable이기 빼문에 반복문에서 +=을 사용하면 누적 복사로 최악의 경우 발생.

-> join은 모든 문자열 길이를 미리 계산해서, 정확히 한 번 메모리를 할당하고 한 번만 복사한다.