[코딩테스트] 프로그래머스 [3차] 압축 파이썬(Python)

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

프로그래머스

해당 문제는 카카오에서 출제한 코딩테스트 문제입니다.

문제의 전체해설은 링크에서 확인할 수 있습니다.

 

해설을 간단하게 요약하면 설명에 나온 의사코드(Pseudocode)를 그대로 따라서 구현만 하면 되는문제입니다.

첫 번째 방법

from collections import deque
def solution(msg):
    alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    dic = {}
    for i, c in enumerate(alphabet):
        dic[c] = i+1
    msg = deque(msg)
    while msg:
        for i in range(len(msg), 0, -1):
            word = ''.join(list(msg)[:i])
            if dic.get(word) != None:
                result.append(dic[word])
                add_word = ''.join(list(msg)[:i+1])
                dic[add_word] = len(dic) + 1
                break
        for _ in range(len(word)):
            msg.popleft()
    return result

첫 번째 풀이 방법은 deque 자료구조를 이용한 방법입니다.

먼저 alphabet을 딕셔너리(dic)로 초기화 해준 뒤에 주어진 msg를 deque 자료구조로 변환해줍니다.

 

msg가 빌때까지 반복문(while)을 실행합니다.

msg를 전체문자부터 하나씩 줄여가며 확인을 했습니다.

예를 들어 s = 'KAKAO'라고 가정하면

word = 'KAKAO'로 딕셔너리에 'KAKAO'가 존재하는지 확인합니다.

- 딕셔너리의 get(word)함수는 word가 딕셔너리에 존재하면 value값을 반환하고 존재하지 않는다면 None을 반환하게 됩니다.

'KAKAO'는 딕셔너리에 존재하지 않기 때문에 넘어갑니다.

'KAKAO' 단어에서 한글자 줄여 'KAKA'를 확인합니다 역시 존재하지 않습니다.

'KAK', 'KA' 또한 존재하지 않기 때문에 넘어갑니다.

'K'는 딕셔너리에 존재하기 때문에 조건문에 들어갑니다.

결과(result)에 딕셔너리의 key로 'K' 해당하는 value를 꺼내어 저장합니다.

msg[:i+1]인  'KA'(이전단어)를 딕셔너리에 등록합니다.

그리고 해당 반복문을 빠져나오고 확인한 글자 수 만큼 popleft()합니다.

msg = 'AKAO'가 됩니다.

마지막으로 반목문(while)을 다 돌면 결과(result)를 반환합니다.

두 번째 방법

두 번째 풀이 방법은 다른 사람의 코드를 참고하여 만들었습니다.

def solution(msg):
    alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    dic = {}
    for i, c in enumerate(alphabet):
        dic[c] = i+1
    
    result = []
    while True:
        #전체 단어가 딕셔너리에 등록되어 있는 경우
        if dic.get(msg):
            result.append(dic[msg])
            break
        for i in range(1, len(msg)+1):
            s = msg[:i]
            # 딕셔너리에 없을 경우
            if dic.get(s) == None:
                #이전 단어
                p = msg[:i-1]
                #이전단어를 딕셔너리에서 찾아서 결과로 등록
                result.append(dic[p])
                #현재 단어를 새롭게 등록
                dic[s] = len(dic) + 1
                msg = msg[i-1:]
                break
    return result

첫 번째 풀이 방법과 마찬가지로 alphabet을 딕셔너리(dic)로 초기화 해준 뒤에 주어진 msg를 deque 자료구조로 변환해줍니다.

 

반복문(while)을 실행하는데 반복문(while)의 종료조건은 msg가 딕셔너리에 등록되어 있는 경우 종료합니다.

이때 결과(result)에 딕셔너리에 등록되어 있는 msg에 해당하는 value를 저장하고 whiel문을 탈출합니다.

 

msg가 딕셔너리에 등록되어 있지 않다면 

첫 번째 방법과는 다르게 글자를 하나씩 증가시키며 확인합니다.

예를들어 msg = 'KAKAO'라고 가정하면

s = 'K'로 시작합니다. 'K'는 딕셔너리에 등록되어 있기 때문에 넘어가고

s= 'KA'로 변경이됩니다.

'KA'는 딕셔너리에 등록되어 있지 않기 때문에 조건문으로 들어갑니다.

- 딕셔너리의 get(s)함수는 s가 등록되어 있지 않다면 None을 반환합니다.

msg[:i-1]인 'K'(이전단어)를 key로 하는 딕셔너리의 value 값을 결과(result)에 저장합니다.

'KA'(현재단어)를 딕셔너리에 새롭게 등록합니다.

msg = 'AKAO'로 변경하고 반복문(for)를 탈출합니다.

 

반목문(while)이 종료되면 결과(result)를 반환합니다.

 

첫 번째 방법과 다르게 두 번째 방법이 더 빠른 실행속도를 보여줍니다.

첫 번째 방법은

1. 전체문자부터 확인하여 글자를 하나씩 줄여가는 과정

2. deque 자료구조를 list로 변경하고 join문을 사용하는 과정이 존재

3. 단어의 크기만큼 popleft() 함수을 실행

위의 세 가지 방법으로 인하여 실행속도 늦어지는 것으로 보입니다.