deque 잘 활용하기

1. 문제

 

https://programmers.co.kr/learn/courses/30/lessons/17684?language=python3 

코딩테스트 연습 - [3차] 압축

 

신입사원 어피치는 카카오톡으로 전송되는 메시지를 압축하여 전송 효율을 높이는 업무를 맡게 되었다.

 

메시지를 압축하더라도 전달되는 정보가 바뀌어서는 안되므로, 압축 전의 정보를 완벽하게 복원 가능한 무손실 압축 알고리즘을 구현하기로 했다.

 

어피치는 여러 압축 알고리즘 중에서 성능이 좋고 구현이 간단한 LZW 압축을 구현하기로 했다.

 

LZW 압축은 1983년 발표된 알고리즘으로 이미지 파일 포맷인 GIF등 다양한 응용에서 사용되었다.

 

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

 

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

 

2) 사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다

 

3) w에 해당하는 사전의 색인 번호를 출력하고, 입력에서 w를 제거한다

 

4) 입력에서 처리되지 않은 다음 글자가 남아있다면(c), w+c에 해당하는 단어를 사전에 등록한다

 

5) 단계 2로 돌아간다

 

압축 알고리즘이 영문 대문자만 처리한다고 할 때, 사전은 다음과 같이 초기화된다.

 

사전의 색인 번호는 정수값으로 주어지며, 1부터 시작한다고 하자

 

 

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

 

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

 

 

2. 예시

 

 

 

 

 

3. 나의 풀이

 

일단 사전을 초기화하고 pop을 써야할 것 같으니까 시간을 줄이기 위해 deque를 만들어

 

def solution(msg):
    
    answer = []
    
    from collections import deque
    
    alpha_dic = {'A':1, 'B':2, 'C':3, 'D':4, 'E':5,
    'F':6, 'G':7, 'H':8, 'I':9, 'J':10, 'K':11, 'L':12,
    'M':13, 'N':14, 'O':15, 'P':16, 'Q':17, 'R':18, 'S':19,
    'T':20, 'U':21, 'V':22, 'W':23, 'X':24, 'Y':25, 'Z':26}
    
    max_ind = 26
    
    deque_msg = deque(msg)

 

다음 규칙에 맞게 deque_msg에서 한글자씩 빼내기 시작한다

 

한글자 뺄때마다 사전에서 검색을 해서 value가 존재하는지 확인

 

while len(deque_msg) != 0:
    
    s= ''
    
    while len(deque_msg) != 0:
        
        s += deque_msg.popleft()
        
        try:
        
           ind = alpha_dic[s]
           
       except:
           
           answer.append(ind)
           
           max_ind += 1
           
           alpha_dic[s] = max_ind
           
           deque_msg.appendleft(s[-1])
           
           break
           
answer.append(ind)

return answer

 

try를 통해서 빼낸 문자가 alpha_dic에 존재하면 ind에 value가 저장이 될거고 다음 반복문으로 넘어감

 

사전에 key가 존재하는지 아닌지 검사하는 방법으로 try ~ except~가 유용하다

 

예를 들어 KAKAO같은 경우 K가 존재하니까 ind에는 K의 value가 넘어감

 

다음 반복문으로 넘어가면 이제 deque_msg의 글자가 하나 더 빠져서 s에 붙어

 

deque_msg에는 AKAO가 있어서 A가 빠져서 s에 KA가 된다

 

그러면 alpha_dic에 KA의 value가 있는지 다시 한번 검사해보고 없으면 except로 넘어감

 

KA는 없으니까 except문으로 넘어갈건데

 

여기서 중요한건 ind에는 K의 index가 저장이 되어서 answer에 그대로 index를 집어넣으면 돼

 

KA를 사전에 추가해야하는데 규칙에 따라

 

현재 사전의 max_ind=26에 1을 더한 27을 새롭게 alpha_dic에 넣고

 

규칙에 따라 마지막으로 들어왔던 두번째 글자인 A는 다시 deque_msg에 넣어줘야함

 

마지막으로 들어간 글자는 s[-1]을 이용하면 s의 길이에 무관하게 뺄 수 있다

 

사전에 추가가 끝나면 중간 반복문을 탈출하고 다시 반복문을 처음부터 돌거임

 

---------------------------------------------------------------------------------------------------------

 

s는 초기화한 뒤에 s에 A를 붙이고

 

A는 존재하니까 ind에 A의 index가 들어가고

 

AK는 존재하지 않으니까 AK를 사전에 max_ind=27에 1을 더한 28로 추가하고 현재 index인 A의 index를 answer에 추가

 

마지막으로 들어온 K는 다시 deque_msg에 넣는다

 

--------------------------------------------------------------------------------------------------------

 

다시 반복문을 돌아서 KAO부터 돌거임

 

K는 존재하니까 ind에 K의 index가 저장, 다시 A가 빠져서 KA는 사전에 존재하니 ind에 KA의 index가 저장

 

다시 O가 빠져서 KAO는 사전에 존재하지 않으니 max_ind=28에 1을 더한 29로 추가. 현재 index인 KA의 index를 answer에 추가

 

마지막으로 빠진 O는 다시 deque_msg에 저장하고 처음부터 반복문 돌아

 

O가 빠져나오면 사전에 존재하니 ind가 저장이 될거고… 이제 ,deque_msg에 문자가 존재하지 않으니 반복문 빠져나와

 

현재 ind에 저장된 index를 answer에 추가하고 그대로 return하면 끝

 

 

4. 다른 풀이

 

알고리즘에 맞게 침착하고 논리적으로 잘 풀었다고 생각한다

 

사전 초기화를 어떤식으로 하는지 몇가지 살펴보면 좋을듯

 

tmp = {chr(e+64): e for e in range(1,27)}

myDic = dict(zip('ABCDEFGHIJKLMNOPQRSTUVWXYZ', range(1,27)))

alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

d = {k:v for (k,v) in zip(alphabet, list(range(1,27)))}

 

chr()은 아스키 코드값을 문자로 바꿔주는 함수

 

65부터 대문자 A인듯

 

혹은 zip을 이용해서 ABCD~XYZ 문자열이랑 range(1,27)을 같이 돌아서 사전으로 구성하는 방법도 멋지네

 

def solution(msg):
    
    answer = []
    
    tmp = {chr(e+64): e for e in range(1,27)}
    
    num = 27
    
    while msg:
        
        tt = 1
        
        while msg[:tt] in tmp.keys() and tt <= msg.__len__():
            
            tt += 1
            
        tt -= 1
        
        if msg[:tt] in tmp.keys():
            
            answer.append(tmp[msg[:tt]])
            
            tmp[msg[:tt+1]] = num
            
            num += 1
            
        msg = msg[tt:]
        
    return answer

 

아무튼 사전을 구성하고 나서 while msg:를 이용해 반복을 하는데

 

while msg:는 msg에 문자가 존재하면 True이고 문자가 존재하지 않으면 False라서… 이것도 좀 멋지네 len으로 하는것보다 효율적일듯

 

tt=1을 이용해서 문자를 하나씩 뺀다는 의미로 가는듯

 

msg[:tt]하면 tt=1이면 문자 하나를 빼는건데

 

뺀 문자가 사전의 key인 tmp.keys()에 존재하는지 검사하고

 

tt <= msg.__len__()...???  여기서 msg.__len__()은 len(msg)인듯

 

아무튼 뺀 문자가 사전에 존재하면 tt에 1을 더해서 문자를 하나 더 빼겠다는 의미로 반복문을 돌거고

 

만약 문자가 tmp에 존재하지 않으면 안에 있는 반복문을 빠져나온다음에..

 

tt에 1을 빼서.. 마지막으로 들어온 문자는 다시 msg에 넣어줄거임

 

사실 이러면 deque에 넣고 빼는 과정이 없어서 오히려 더 좋을수도?

 

그리고 마지막으로 들어온 문자를 뺀 문자의 사전 index를 answer에 넣어주고

 

마지막으로 들어온 문자를 추가한 문자를 사전의 max_index보다 1 큰 num을 value로 하여 추가를 하네

 

그리고 마지막에 msg=msg[tt:]로 실제로 answer에 넣었으면 제거를 해서 다시 반복문을 돌도록

 

 

5. 되돌아보기

 

알고리즘에 맞게 논리적으로 침착하게 코딩한거 좋았다

 

 

5-1) 시간을 줄일려고 deque로 pop을 한다는 생각하는거 좋았다

 

사전을 어떻게 초기화했는지 살펴보면 좋을 것 같다

 

 

5-2) list comprehension말고도 dict comprehension도 가능하거든

 

deque를 써서 풀긴했지만 안쓰고도 풀어낸 다른 풀이의 아이디어를 잘 살펴보면 좋을것 같고

 

while len(msg): 이렇게 생각하는 경향이 있는데

 

 

5-3) 이걸 while msg: 이렇게 바꿔보는거 어떨까?

 

 

5-4) deque를 쓰지 않고 문자를 뺄때 msg[:1]로 하나씩 뺄 수 있기도 하고

 

msg[:tt]에서 tt+=1로 문자를 추가 시켜나갈 수 있는데

 

뺀 문자를 다시 넣을려면 tt-=1만 하면 되니까 오히려 더 좋을수도 있겠는데