압축 (Programmers 17684)

문파이더맨·2021년 7월 17일
0

Algorithm

목록 보기
56/58
post-thumbnail

🧑‍💻 압축

  • 신입사원 어피치는 카카오톡으로 전송되는 메시지를 압축하여 전송 효율을 높이는 업무를 맡게 되었다. 메시지를 압축하더라도 전달되는 정보가 바뀌어서는 안 되므로, 압축 전의 정보를 완벽하게 복원 가능한 무손실 압축 알고리즘을 구현하기로 했다.
  • 어피치는 여러 압축 알고리즘 중에서 성능이 좋고 구현이 간단한 LZW(Lempel–Ziv–Welch) 압축을 구현하기로 했다. LZW 압축은 1983년 발표된 알고리즘으로, 이미지 파일 포맷인 GIF 등 다양한 응용에서 사용되었다.
  • LZW 압축은 다음 과정을 거친다.
    • 길이가 1인 모든 단어를 포함하도록 사전을 초기화한다.
    • 사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다.
    • w에 해당하는 사전의 색인 번호를 출력하고, 입력에서 w를 제거한다.
    • 입력에서 처리되지 않은 다음 글자가 남아있다면(c), w+c에 해당하는 단어를 사전에 등록한다.
    • 2단계로 돌아간다.
  • 압축 알고리즘이 영문 대문자만 처리한다고 할 때, 사전은 다음과 같이 초기화된다. 사전의 색인 번호는 정수값으로 주어지며, 1부터 시작한다고 하자.
색인 번호123...242526
단어ABC...XYZ
  • 예를 들어 입력으로 KAKAO가 들어온다고 하자.
    • 현재 사전에는 KAKAO의 첫 글자 K는 등록되어 있으나, 두 번째 글자까지인 KA는 없으므로, 첫 글자 K에 해당하는 색인 번호 11을 출력하고, 다음 글자인 A를 포함한 KA를 사전에 27 번째로 등록한다.
    • 두 번째 글자 A는 사전에 있으나, 세 번째 글자까지인 AK는 사전에 없으므로, A의 색인 번호 1을 출력하고, AK를 사전에 28 번째로 등록한다.
    • 세 번째 글자에서 시작하는 KA가 사전에 있으므로, KA에 해당하는 색인 번호 27을 출력하고, 다음 글자 O를 포함한 KAO를 29 번째로 등록한다.
    • 마지막으로 처리되지 않은 글자 O에 해당하는 색인 번호 15를 출력한다.
현재 입력(w)다음 글자(c)출력사전 추가(w+c)
KA1127:KA
AK128:AK
KAO2729:KAO
O15
  • 이 과정을 거쳐 다섯 글자의 문장 KAKAO가 4개의 색인 번호 [11, 1, 27, 15]로 압축된다.
  • 입력으로 TOBEORNOTTOBEORTOBEORNOT가 들어오면 다음과 같이 압축이 진행된다.
현재 입력(w)다음 글자(c)출력사전 추가(w+c)
TO2027:TO
OB1528:OB
BE229:BE
EO530:EO
OR1531:OR
RN1832:RN
NO1433:NO
OT1534:OT
TT2035:TT
TOB2736:TOB
BEO2937:BEO
ORT3138:ORT
TOBE3639:TOBE
EOR3040:EOR
RNO3241:RNO
OT34

입력형식

입력으로 영문 대문자로만 이뤄진 문자열 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]

🧑‍💻 해결방법

  • 알파벳이 key, 알파벳의 순서를 value로 설정한 dictionary를 하나 만든다.
  • 입력받은 문자열을 탐색 받되, buffer 변수를 활용해서 다음 값과 이어준다.

🧑‍💻 코드

def solution(msg):
   answer = []
   dic_al = {
       '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
   }
   dic_size = 26
   buffer = ""
   for al in msg:
       test = buffer + al
       if test in list(dic_al.keys()):
           buffer = test
       else:
           answer.append(dic_al[buffer])
           dic_size += 1
           dic_al[test] = dic_size
           buffer = al
   if buffer:
       answer.append(dic_al[buffer])

   return answer

🧑‍💻 총평

  • 로직 구상은 간단했지만 어떻게 짜야할지 고민하는 마당에 빈 문자열에 추가시켜줄 것을 생각했다.
  • 어제 문자열 문제도 그렇고 문자열 문제들은 대체로 비슷한 듯하다.
  • 연습에 연습을 거치자
profile
Sever 개발할래요.

0개의 댓글