압축(2018 KAKAO BLIND RECRUITMENT) - 파이썬

dict = [chr(ord("A")+i) for i in range(0,26)]

def solution(msg):
    answer = []
    first = 0    
    last = 0
    tmp = 0
    while last < len(msg): 
        if msg[first:last+1] in dict:
            tmp = dict.index(msg[first:last+1])
            last += 1 
        else:
            answer.append(tmp + 1)
            dict.append(msg[first:last+1])
            first = last
    answer.append(tmp + 1)
    return answer

문제요약

LZW(Lempel–Ziv–Welch) 압축을 구현을 구현하시오.

설명

dict = [chr(ord("A")+i) for i in range(0,26)]

A-Z 까지를 dict배열에 넣어 주었다.

 

    while last < len(msg): 
        if msg[first:last+1] in dict:
            tmp = dict.index(msg[first:last+1])
            last += 1 
        else:
            answer.append(tmp + 1)
            dict.append(msg[first:last+1])
            first = last
    answer.append(tmp + 1)

last가 len보다 작을 때 까지만 반복한다.

 

만약! 들어온 문자열이 dict안에 있다면 if가 true이다. (슬라이스를 이용하였다.)

 

예를들어 보자

 

이론대로라면 KAKAO가 있을 때, dict에서 27은 KA 28은 AK이다.

두번째 K가 들어왔을때 K는 있기 때문에 if문에 들어가 last가 1 증가한다.

두번째 K와 그 다음 A가 합쳐져 KA 가 들어왔을때 if문에 들어가 last가 1 증가한다.

KA와 그다음인 O가 합쳐져 KAO 들어왔을 때, KAO는 없기때문에 if에 만족하지 않는다.

 

else에 들어가 answer 에 KA의 인덱스 + 1을 넣고, 사전에 맨 마지막에 KAO를 추가한다.

그다음 시작 지점을 변경해주며 넘어간다.

 

반복문에 조건을 last로 하게된다면, 맨마지막의 tmp는 무시되게 된다.

따라서 마지막에 한번 tmp+1를 추가시켜줌으로써 원하는 답을 얻을 수 있다.