새싹프로그래머의 이야기

문제: LZW 압축

풀이 코드:

import string


def solution(msg):
    answer = []
    alphabet = list(string.ascii_uppercase)
    dic = {c: i + 1 for i, c in enumerate(alphabet)}
    pos = 27

    while msg:
        length = 1

        while msg[:length] in dic.keys() and length <= len(msg):
            length += 1
        if msg[:length] not in dic.keys():
            dic[msg[:length]] = pos
            pos += 1

        answer.append(dic[msg[:length - 1]])
        msg = msg[length - 1:]

    return answer

문제풀이:

alphabet = list(string.ascii_uppercase)
dic = {c: i + 1 for i, c in enumerate(alphabet)}

먼저, 알파벳에 대한 index가 필요하기 때문에 다음과 같이 enumerate 함수를 통해 딕셔너리 형태로 알파벳:index 형태로 저장해주었습니다.

while msg:
    length = 1

    while msg[:length] in dic.keys() and length <= len(msg):
        length += 1
    if msg[:length] not in dic.keys():
        dic[msg[:length]] = pos
        pos += 1

    answer.append(dic[msg[:length - 1]])
    msg = msg[length - 1:]

가장 핵심이 되는 코드는 문제 조건에 따라 다음과 같이 구현하였습니다.

• 문자열의 시작점으로부터 문자를 탐색하여 딕셔너리에 담긴 최대 길이의 문자열을 구합니다. 즉, 해당 문자열에 한 글자가 추가된다면 해당 문자열은 딕셔너리에 담기지 않은 문자열이 됩니다.
• 딕셔너리에 담기지 않는 문자열에 대해서는 새로운 index와 함께 딕셔너리에 추가해줍니다.
• 딕셔너리에 담긴 최대 길이 문자열에 대한 index를 answer 배열에 담습니다.

위 과정을 반복하여, 문자열을 압축합니다.