프로그래머스 Lv2 압축

2018 KAKAO BLIND RECRUITMENT 문제로 LZW 압축을 구현하는 문제이다.

 

문제 풀이

 1. 먼저 각 문자열에 대한 색인 번호를 넣을 사전을 선언한다.

 2. A - Z 까지를 색인 번호 1 - 26 으로 넣어준다.

 3. 맨 앞 문자부터 사전에서 찾아보며 사전에 있으면 문자열의 길이를 늘려가며 찾는다. 문자열이 사전에서 없어지면 해당 문자열을 색인번호의 최댓값에 1을 더해 넣는다. 

 4. 3과정에서 사전에 있는 가장 긴 문자열을 answer에 넣는다.

 5. 다음 문자부터 3-4과정을 반복한다.

 예를 들면, 'KAKAO'의 경우, K를 먼저 찾고 있으면 KA를 찾고 또 있으면 KAK를 찾는 식으로 진행하며 해당 문자열이 사전에 없을 때 까지 진행하여, 해당 문자열이 사전에 없으면 사전에 넣고, 다음 문자부터 다시 시작한다. KA까지 사전에 있다면 KAK를 사전에 넣고, KA의 색인 번호를 answer에 넣는다.

Python Code

from string import ascii_uppercase
def solution(msg):
    dic = {}
    idx=1
    for a in ascii_uppercase:
        dic[a] = idx
        idx+=1
    answer = []
 
    i=0
    j=i+1
    while i < len(msg)-1:
        j=i+1
        while j<= len(msg) and msg[i:j] in dic:
            j+=1
        #msg[i:j-1]는 dic에 있다
        answer.append(dic[msg[i:j-1]])
        dic[msg[i:j]]=idx
        idx += 1
        i=j-1
        #print(dic)
    if i == len(msg)-1:
        answer.append(dic[msg[-1]])
    return answer

문제 링크

프로그래머스