[프로그래머스] 압축 / 파이썬 / (딕셔너리)

문제 설명

[3차] 압축

압축

신입사원 어피치는 카카오톡으로 전송되는 메시지를 압축하여 전송 효율을 높이는 업무를 맡게 되었다. 메시지를 압축하더라도 전달되는 정보가 바뀌어서는 안 되므로, 압축 전의 정보를 완벽하게 복원 가능한 무손실 압축 알고리즘을 구현하기로 했다.

어피치는 여러 압축 알고리즘 중에서 성능이 좋고 구현이 간단한LZW(Lempel–Ziv–Welch) 압축을 구현하기로 했다. LZW 압축은 1983년 발표된 알고리즘으로, 이미지 파일 포맷인 GIF 등 다양한 응용에서 사용되었다.

LZW 압축은 다음 과정을 거친다.

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

압축 알고리즘이 영문 대문자만 처리한다고 할 때, 사전은 다음과 같이 초기화된다. 사전의 색인 번호는 정수값으로 주어지며, 1부터 시작한다고 하자.

색인 번호123...242526

단어

A

B

C

...

X

Y

Z

예를 들어 입력으로KAKAO가 들어온다고 하자.

1. 현재 사전에는KAKAO의 첫 글자K는 등록되어 있으나, 두 번째 글자까지인KA는 없으므로, 첫 글자K에 해당하는 색인 번호 11을 출력하고, 다음 글자인A를 포함한KA를 사전에 27 번째로 등록한다.
2. 두 번째 글자A는 사전에 있으나, 세 번째 글자까지인AK는 사전에 없으므로,A의 색인 번호 1을 출력하고,AK를 사전에 28 번째로 등록한다.
3. 세 번째 글자에서 시작하는KA가 사전에 있으므로,KA에 해당하는 색인 번호 27을 출력하고, 다음 글자O를 포함한KAO를 29 번째로 등록한다.
4. 마지막으로 처리되지 않은 글자O에 해당하는 색인 번호 15를 출력한다.

현재 입력(w)다음 글자(c)출력사전 추가(w+c)

K	A	11	27: KA
A	K	1	28: AK
KA	O	27	29: KAO
O	15

이 과정을 거쳐 다섯 글자의 문장KAKAO가 4개의 색인 번호 [11, 1, 27, 15]로 압축된다.

입력으로TOBEORNOTTOBEORTOBEORNOT가 들어오면 다음과 같이 압축이 진행된다.

현재 입력(w)다음 글자(c)출력사전 추가(w+c)

T	O	20	27: TO
O	B	15	28: OB
B	E	2	29: BE
E	O	5	30: EO
O	R	15	31: OR
R	N	18	32: RN
N	O	14	33: NO
O	T	15	34: OT
T	T	20	35: TT
TO	B	27	36: TOB
BE	O	29	37: BEO
OR	T	31	38: ORT
TOB	E	36	39: TOBE
EO	R	30	40: EOR
RN	O	32	41: RNO
OT	34

입력 형식

입력으로 영문 대문자로만 이뤄진 문자열msg가 주어진다.msg의 길이는 1 글자 이상, 1000 글자 이하이다.

출력 형식

주어진 문자열을 압축한 후의 사전 색인 번호를 배열로 출력하라.

입출력 예제

msganswer

KAKAO	[11, 1, 27, 15]
TOBEORNOTTOBEORTOBEORNOT	[20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34]
ABABABABABABABAB	[1, 2, 27, 29, 28, 31, 30]

풀이

우선 문제에서 정의한 dictionary를 먼저 초기화해준다.

그 후 일종의 Two Pointer 개념으로 풀었는데, Msg의 시작점에서부터 Dictionary에 일치하는 문자열이 있는지 확인한다.

딕셔너리 일치하는 문자열이 있으면, 딕셔너리에 존재하지 않는 문자열이 나올때까지 길이를 하나씩 더 늘린다.

문자열이 딕셔너리에 존재하지 않는 순간, 일치하는 문자열까지를 딕셔너리에 새로 추가해주고, Msg의 시작점을 옮겨준다.

그리고 종료조건을 하나 추가해주었다. (사실 이 부분이 굉장히 마음에 들지 않는데, 어떻게하면 더 깔끔하게 짤 수 있는지 고민중이다.)

def solution(msg):
    dict = {chr(ord('a') + i - 1) : i for i in range(1, 27) }

    cnt = 27
    answer = []
    msg = msg.lower()
    i = 0

    while i < len(msg):
        for j in range(i+1, len(msg) + 1):
            if msg[i:j] not in dict:
                dict[msg[i:j]] = cnt
                cnt += 1
                answer.append(dict[msg[i:j-1]])
                i = j - 1
                break
            else:
                if j == len(msg):
                    answer.append(dict[msg[i:j]])
                    i = len(msg)
    return answer

다른 풀이로는?

while True:
        if msg in d:
            answer.append(d[msg])
            break
        for i in range(1, len(msg)+1):
            if msg[0:i] not in d:
                answer.append(d[msg[0:i-1]])
                d[msg[0:i]] = len(d)+1
                msg = msg[i-1:]
                break

msg 크기 자체를 줄이면서 푸는 방법이다.
이 코드는 성능이 최적화되는건 아니지만, 내가 작성한 while문보다 가독성도 좋고, 코드도 짧아서 가져와보았다.