[프로그래머스] [3차] 압축

문제

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

어피치는 메신저에서 전송되는 메시지를 압축해 전송 효율을 높이는 업무를 맡았다. 메시지를 압축해도 전달하는 정보가 변경되서는 안 되기 때문에 압축 전 정보를 복원할 수 있는 여러 가지 무손실 압축 알고리즘 중, 성능이 좋고 구현하기 좋은 LZW(Lempel–Ziv–Welch) 압축을 구현하기로 했다. LZW 압축은 1983년에 발표된 알고리즘으로, 이미지 파일 포맷 GIF 등에서 사용된다.

 

압축 과정은 다음과 같다.

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

압축 알고리즘이 영문 대문자만 처리한다고 할 때, 알파벳 A부터 Z는 1부터 26으로 초기화된다. 예로 들어, 문자열 KAKAO를 처리한다고 할 때, 다음과 같이 처리된다.

현재 입력(w)	다음 글자(c)	출력	사전 추가(w+c)
K	A	11	27: KA
A	K	1	28: AK
KA	O	27	29: KAO
O		15

 

문자열을 압축한 후의 사전 색인 번호 배열을 출력하는 함수를 구현하라.

 

 

풀이

동작 방식 상 사전에 가장 마지막에 추가되는 단어가 가장 긴 단어에 해당된다. 그래서 입력 문자열에서 일치 문자열을 찾을 때 사전에 추가된 단어를 역순으로 확인한다.

 

구현

1. 길이가 1인 모든 단어를 포함하도록 사전을 초기화한다.

zip_dict = {i: ord(i) - 64 for i in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'}

 

2. 사전의 가장 마지막 단어부터 시작해 단어가 입력 문자열의 시작과 일치하는지 확인한다.

list_key = list(zip_dict.keys())[::-1]
    for k in list_key:
        if msg.startswith(k):

 

3. 단어가 일치하면, 결과값 리스트에 추가하고, 입력 문자열에서 단어를 삭제한다.

answer.append(zip_dict[k])
msg = msg.replace(k, '', 1)

 

4. 입력 문자열이 남아있으면, 현재 단어와 입력 문자열의 첫 글자를 사전에 추가하고, 다음 반복으로 넘어간다.

if msg:
    zip_dict[k + msg[0]] = len(list_key) + 1
break

 

5. 2부터의 과정을 입력 문자열이 빌 때까지 반복한다. 반복문이 완료되면 결괏값을 반환한다.

전체 구현 코드는 아래와 같다.

def solution(msg):
    zip_dict = {i: ord(i) - 64 for i in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'}
    answer = []
    while msg:
        list_key = list(zip_dict.keys())[::-1]
        for k in list_key:
            if msg.startswith(k):
                answer.append(zip_dict[k])
                msg = msg.replace(k, '', 1)
                if msg:
                    zip_dict[k + msg[0]] = len(list_key) + 1
                break
    return answer

 

 

참고 문서

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