[프로그래머스] 압축 - python

압축

문제

LZW 압축은 다음 과정을 거친다.

1. 길이가 1인 모든 단어를 포함하도록 사전을 초기화한다.
2. 사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다.
3. w에 해당하는 사전의 색인 번호를 출력하고, 입력에서 w를 제거한다.
4. 입력에서 처리되지 않은 다음 글자가 남아있다면(c), w+c에 해당하는 단어를 사전에 등록한다.
5. 단계 2로 돌아간다.

주어진 문자열을 압축한 후의 사전 색인 번호를 배열로 출력하라.

제한사항

• 입력으로 영문 대문자로만 이뤄진 문자열 msg가 주어진다. msg의 길이는 1 글자 이상, 1000 글자 이하이다.

풀이

처음에는 재귀로 구현했다가 너무 느려서 반복문으로 바꿨다.

1. 사전에 존재하는 가장 긴 배열을 찾는다. (w)
2. 나머지 글자 한 개를 더한 값을 사전에 등록한다. (w + c )
3. 해당 문자의 색인번호를 answer에 넣는다.
4. msg에서 w를 제거한다.

def solution(msg):
    answer = []
    dictionary = {chr(i + 65): i + 1 for i in range(0, 27)}
    i = 0
    while msg:
        j = i + 1
        while msg[i : j] in dictionary.keys() and j <= len(msg):
            j += 1
        
        if msg[i : j] not in dictionary.keys():
            dictionary[msg[i : j]] = len(dictionary)
        
        answer.append(dictionary[msg[i : j - 1]])
        msg = msg[j - 1:]
        
    return answer