- 신입사원 어피치는 카카오톡으로 전송되는 메시지를 압축하여 전송 효율을 높이는 업무를 맡게 되었다. 메시지를 압축하더라도 전달되는 정보가 바뀌어서는 안 되므로, 압축 전의 정보를 완벽하게 복원 가능한 무손실 압축 알고리즘을 구현하기로 했다.
- 어피치는 여러 압축 알고리즘 중에서 성능이 좋고 구현이 간단한 LZW(Lempel–Ziv–Welch) 압축을 구현하기로 했다. LZW 압축은 1983년 발표된 알고리즘으로, 이미지 파일 포맷인 GIF 등 다양한 응용에서 사용되었다.
- LZW 압축은 다음 과정을 거친다.
- 길이가 1인 모든 단어를 포함하도록 사전을 초기화한다.
- 사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다.
- w에 해당하는 사전의 색인 번호를 출력하고, 입력에서 w를 제거한다.
- 입력에서 처리되지 않은 다음 글자가 남아있다면(c), w+c에 해당하는 단어를 사전에 등록한다.
- 2단계로 돌아간다.
- 압축 알고리즘이 영문 대문자만 처리한다고 할 때, 사전은 다음과 같이 초기화된다. 사전의 색인 번호는 정수값으로 주어지며, 1부터 시작한다고 하자.
색인 번호 1 2 3 ... 24 25 26 단어 A B C ... X Y Z
- 예를 들어 입력으로 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) 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 글자 이하이다.
출력형식
주어진 문자열을 압축한 후의 사전 색인 번호를 배열로 출력하라.
입출력 예제
msg answer 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
- 로직 구상은 간단했지만 어떻게 짜야할지 고민하는 마당에 빈 문자열에 추가시켜줄 것을 생각했다.
- 어제 문자열 문제도 그렇고 문자열 문제들은 대체로 비슷한 듯하다.
- 연습에 연습을 거치자