[programmers/py] 3차 압축

3차 압축

https://school.programmers.co.kr/learn/courses/30/lessons/17684?language=javascript

문제 설명

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

영문 대문자만 처리한다고 할 때, 사전은 다음과 같이 초기화된다. 사전의 색인 번호는 정수값으로 주어지며, 1부터 시작한다고 하자.

풀이

• case 사전에 없음
  사전에 w+c 추가
  w+c[:-1]를 통해 마지막 글자를 제외한 alpha.index(w)를 answer에 추가
  w = 현재 msg[i]로 변경

만약 추가하지 못한 값이 있다면 추가한다.

def solution(msg):
    aaaa = "0ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    alpha = list(aaaa)
    answer = []
    
    s = ""
    
    for i in range(len(msg)):
        s += msg[i] # K, KA, KAO 계속 추가됨
        
        if not s in alpha:
            answer.append(alpha.index(s[:-1]))
            alpha.append(s)
            s = msg[i]
    if s : answer.append(alpha.index(s))
    return answer