[코딩테스트] 2018 KAKAO BLIND RECRUITMENT - [3차] 압축

---

문제

 

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

프로그래머스

 

LZW 압축을 구현하는 문제

 

사전에 기본 알파벳을 추가하고 첫 글자부터 시작해서 다음글자를 포함한 단어가 등록되어 있지 않다면 사전에 추가해 반복되는 단어를 확장하는 식으로 압축을 진행한다.

 

 

 

 

---

전략

 

01. 딕셔너리

 

 while문을 이용해 겹치는 단어 중 가장 긴 단어까지 찾아내고 그 단어의 인덱스를 answer에 출력한 뒤, 그 다음 글자가 남아 있다면 그 글자를 포함한 새로운 단어를 사전에 딕셔너리에 등록한다. 이를 반복해 압축을 진행.

 

 

 

---

풀이

 

def solution(msg):
    my_dict = {chr(i + 65) : i + 1  for i in range(26)}
    new_index = 27
    answer = []
    i = 0

    while i < len(msg):
        cache = msg[i]


        while my_dict.get(cache):
            if i >= len(msg) - 1:
                i += 1
                answer.append(my_dict[cache])
                break

            else:
                i += 1
                cache += msg[i]

        if i < len(msg):
            answer.append(my_dict[cache[:-1]])

        my_dict[cache] = new_index
        new_index += 1

    return answer

 

 우선 기본 알파벳을 포함한 사전을 만들 때, chr()함수를 사용했다. ASCII코드를 알파벳으로 바꾸는 함수인데 value값에 인덱스를 차례로 넣기 쉽게 사용했다. 만약 이 함수를 사용하지 않았다면 string = 'ABC...YZ' 이런 식으로 별도의 문자열을 만든 뒤 enumerate()함수를 이용해 인덱스와 매핑해서 집어넣으면 된다. 그것도 아니면 그냥 for문으로 for i in range(1, 27)까지 하나씩 집어넣어도 된다.

 

 다음으로 사전에 새롭게 추가될 단어의 인덱스를 나타내기 위해 new_index변수를 만들어주었다. 만약 새로운 단어가 사전에 추가되면 +1씩 증가된다.

 

 그리고 msg를 차례차례 읽어나가다가 사전에 있는 가장 긴 단어를 answer에 저장한 뒤 그 다음 인덱스로 바로 넘어가기 위해 i = 0으로 초기화하고 while문을 이용했다.

 

 

while my_dict.get(cache):
        if i >= len(msg) - 1:
            i += 1
            answer.append(my_dict[cache])
            break

        else:
            i += 1
            cache += msg[i]

 

 나는 이중 while문을 사용했는데 바깥쪽 while문은 msg를 끝까지 읽기 위한 while문이고, 안쪽 while문은 사전과 매치되는 가장 긴 단어를 찾기 위해 사용했다. 이때 안쪽 while문에서 i를 +1씩 증가시키면서 가장 긴 단어가 있는지 체크하는데, 가장 긴 단어가 매치되고 나서 다시 i가 +1된 시점에서 while문이 중단되므로 가장 마지막 단어에서 i가 걸려 있다면 else문 내부의 코드가 IndexError를 발생시킬 수 있다. 따라서 if문 내부에서 인덱스인 i가 마지막 단어를 가리키는지 체크하고 만약 마지막 단어를 가리킨다면 그 값은 answer에 바로 포함시키고 전체 while문을 빠져나오도록 했다.

 

 

if i < len(msg):
        answer.append(my_dict[cache[:-1]])

 

 여기에선 cache에는 사전에 등록되어야 할 값, 즉 사전에는 없는 새로운 단어(기존 단어 + a)가 저장되어 있다. 따라서 answer에는 기존 단어를 등록시켜줘야 하므로 cache[:-1]를 my_dict에서 찾아서 넣어주도록 했다. 그리고 i가 증가되는 시점 때문에 조건문으로 인덱스의 위치를 체크해주었다.

 

 

my_dict[cache] = new_index
new_index += 1

 

마지막으로 새로운 단어를 위한 new_index를 새로운 단어에 부여하고 my_dict에 저장해준 뒤 new_index를 +1시켜 다음 단어를 준비해준다.

 

정확성 테스트

 

 

---

다른 사람의 풀이

 

1. msg Slicing

 

def solution(msg):
    alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    d = {k:v for (k,v) in zip(alphabet, list(range(1,27)))}
    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

    return answer

 

 내 풀이와 전체적인 개념은 비슷하지만 msg를 읽어나가다가 새로운 단어가 발견됐을 때 그 단어를 등록하고 나서 msg를 slicing해 이미 사용한 문자열을 날려버렸다. 훨씬 더 직관적인 코드인 것 같다. 다만 while True는 예외가 발생할 경우가 너무 많아서 나는 지양한다.

 

 

 

정확성 테스트

 

 

---

추가적인 고찰

 

 LZW 압축 알고리즘에 대해서 더 알아보기로 했다. LZW 압축 알고리즘은 1983년 발표된 알고리즘으로 위 문제에서는 문자열을 압축했지만 더 나아가서 TIFF, GIF등의 이미지 압축 알고리즘의 일부로도 사용되며 많은 문자열로 구성되어 있는 PDF 파일 합축에도 유효하다. 기본적인 개념은 반복되는 데이터를 찾아 이를 더 짧은 코드로 대체하는 것이다. 

 

 이전 글에서 LZW에 대해 언급한 적 있지만 실제로 풀어보니 재밌는 문제였다.