LeetCode의 271번째 문제인 Encode and Decode Strings를 함께 풀어보도록 하겠습니다.
이 문제는 LeetCode에서 유료 구독자만 접근할 수 있습니다. LintCode의 659번째 문제가 거의 동일하며 무료로 푸실 수 있으니 참고 바랍니다.
문제
문자열 목록을 문자열로 인코딩하는 알고리즘을 설계하십시오. 인코딩된 문자열은 네트워크를 통해 전송되고 다시 원래의 문자열 목록으로 디코딩됩니다.
strs[i]에는 256개의 유효한 ASCII 문자 중 어떤 문자든 포함될 수 있습니다.”
예제
입력: ["Hello","World"]
출력: ["Hello","World"]입력: [""]
출력: [""]풀이 1
이 문제는 얼핏 보면 아주 쉬워보일 수 있습니다. 문자열 목록을 문자열로 인코딩할 때 문자 사이에 구분자를 넣으면 될 것 같기 때문입니다.
그런데 여기서 주의할 점은 문자열에 256개의 유효한 ASCII 문자 중 어떤 문자든지 포함될 수 있다는 것인데요. 따라서 반드시 구분 문자(delimiter)로 ASCII 문자가 아닌 문자를 사용해야겠습니다.
우리 채팅할 때 자주 사용하는 이모지로 문자열을 구분해보면 어떨까요?
class Codec:
def encode(self, strs: List[str]) -> str:
return "😄".join(strs)
def decode(self, s: str) -> List[str]:
return s.split("😄")입력 배열이 담고 있는 문자열의 개수를 n라고 했을 때, 이 풀이의 시간 복잡도는 O(n)입니다.
join()과 split() 함수의 수행 시간은 문자열 개수와 비례하기 때문입니다.
별도의 추가 메모리를 사용하는 부분이 없기 때문에 공간 복잡도는 O(1)이 되겠습니다.
풀이 2
위 풀이는 너무 반칙 같으니 좀 더 코딩 테스트에 걸맞는 알고리즘을 생각해보겠습니다.
만약에 구분자를 256개의 ASCII 문자 중 하나를 사용해야한다면 어떻게 해야할까요? 그럼 문자열 안에도 구분자가 들어있을 가능성이 있기 때문에 좀 더 까다로워지겠죠?
예를 들어, 입력으로 다음과 같은 문자열 배열이 -로 문자열을 구분했다고 가정해봅시다.
["Hello", "World","yes-or-no"]위 알고리즘으로 인코드를 한다면 다음과 같은 문자열이 나와서 뭐가 구분자이고 뭐가 문자열의 일부인지 알 수가 없겠죠?
"Hello-World-yes-or-no"만약에 -를 구분자로 디코드를 하면 다음과 같이 5개의 문자열이 나올 것입니다.
입력 배열과 동일하지 않죠.
["Hello", "World", "yes", "or", "no"]어떻게 하면 문자열에 포함되어 있는 구분자와 동일한 문자에서 구분이 되는 것을 피할 수 있을까요?
한 가지 방법은 구분자 이후에 나오는 문자열의 길이도 인코딩 결과에 기록을 해두는 것입니다. 예를 들어, 다음과 같이 문자열 길이를 첨가하여 디코딩을 할 수 있을 것입니다.
"5-Hello5-World9-yes-or-no"그러면 원치 않게 문자열의 중간에서 구분이 될 위험이 사라지게 되겠죠?
--5-- --5-- ----9----
"5-Hello5-World9-yes-or-no"이 알고리즘을 파이썬으로 구현해보겠습니다.
class Codec:
def encode(self, strs: List[str]) -> str:
text = ""
for s in strs:
text += str(len(s)) + "-" + s
return text
def decode(self, s: str) -> List[str]:
strs, i = [], 0
while i < len(s):
delimiter = s.find("-", i) # i부터 첫 구분자 찾음
length = int(s[i:delimiter])
strs.append(s[delimiter + 1 : delimiter + 1 + length])
i = delimiter + 1 + length
return strs이 풀이의 시간 복잡도와 공간 복잡도는 이전 풀이와 동일합니다.
마치면서
이 문제는 Blind 75에 속하는 매우 유명한 문제이지만 저는 개인적으로 그닥 선호하는 문제는 아닙니다. 면접관으로서 지원자의 어떤 능력을 평가하려는 건지 출제 의도가 분명하지 않은 것 같습니다.