[Python] 카카오(2) 압축

https://programmers.co.kr/learn/courses/30/lessons/17684

아이디어

1. 해당 문제는 LZW 압축의 개념을 활용한 문제입니다.
2. 우선 기본 알파벳 사전이 필요합니다. 인덱스가 키가 되는 리스트를 생성합니다.
3. 그 후 주어진 문자열을 한글자씩 순회하며 사전과 비교합니다.
4. 만약 알파벳이라면 사전에서 해당 알파벳의 키(인덱스)를 저장합니다.
5. 그리고 한 글자를 붙여서 그 문자열도 사전에서 찾아봅니다.
6. 사전에 없는 문자열이 나올때까지 반복합니다.
7. 사전에 없는 문자열이 나오면 그 문자열을 사전에 추가합니다.
8. 반복문의 인덱스를 잘 파악한다면 풀 수 있는 문제였습니다.

알게 된 함수/방법

• LZW 압축 : 무손실 압축 기법으로 이미지 파일 포맷인 GIF 등 다양한 응용에서 사용되었다.

정답 코드

def solution(msg):
    dic_list = [chr(i+65) for i in range(26)]
    index_list = []
    i =0

    while i!=len(msg):
        w = msg[i]
        while 1:
            if w in dic_list:
                pre = dic_list.index(w)+1
            else:
                index_list.append(pre)
                dic_list.append(w)
                break
            i += 1
            if i == len(msg):
                index_list.append(pre)
                break
            w += msg[i]

    return index_list