Minystory

Algorithm/Programmers

[프로그래머스/카카오 17684] 압축 (Python)

2022. 8. 9. 09:48

문제 링크 #

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

문제 해설 #

Idea #

LZW 알고리즘 (List로 구현)
단어를 문자 단위로 탐색하면서 캐시에 추가
캐시가 문자 사전에 없을 경우 이전 문자까지의 인덱스를 반환하고 캐시를 문자 사전에 추가

Time Complexity #

Brute-Force: O(N^2) = 1000000

Data Size #

msg: str(1000)

해설 코드 #

python

def solution(msg):
    answer = []
    chars = [chr(x) for x in range(64,91)]

    cache = str()
    for c in msg:
        cache += c
        if cache not in chars:
            answer.append(chars.index(cache[:-1]))
            chars.append(cache)
            cache = c
    answer.append(chars.index(cache))

    return answer