[Level 2] 압축

 

 

 

Algorithm

-  압축 -

 

---

 

문제

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

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

 

어피치는 여러 압축 알고리즘 중에서 성능이 좋고 구현이 간단한 LZM(Lempel-Ziv-Welch) 압축을 구현하기로 했다.

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

 

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

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

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

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

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

5. 단계 2로 돌아간다 

 

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

 

입출력 예시

msg	answer
KAKAO	[11, 1, 27, 25]
TOBEORNOTTOBEORTOBEORNOT	[20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34]

문제 풀기

 

이번 문제는 사실 문제를 읽는데 이해하는데 시간이 너무 오래걸려서 문제에 나와있는 입출력 예시를 보고 문제를 해결해보았다.

(문제 다 풀고 다시 읽어봤지만 문제 자체를 이해하는덴 나에겐 무리인듯... 입출력 예시 짱짱)

 

문제를 어떻게 풀었는지에대해 간단히 설명해보자면 일단 msg로 부터 받아오는 값이 대문자인지 소문자인지 알기 어렵기 때문에 매개변수로 받자마자 소문자로 바꾸고 문제에서 알파벳을 분리해서 번호표사전(?)을 가지고 있어야 하는것 같아서 alpha라는 배열안에 하나씩 알파벳을 넣어서 사전을 만들어 보았다.

 

그리고 나서 msg에서 처음부터 하나씩 alpha에서 값을 찾은다음 다음 문자와 엮어서 사전에 새로 추가해주게 되는데 이때 반복문을 계속 돌리게 될 경우 여러개로 묶여 사전에 등록되어 있는 문자열이 msg안에 포함되어 있을 수 있기 때문에 안쪽 반복문에서 msg를 구간을 계속 나누어 alpha안에 포함되어 있을때 까지 계속 반복문이 돌아가도록 설정을 해주었다.

 

만약 포함되어 있으면 일단 alpha에서 인덱스 값을 찾아서 result안에 인덱스를 넣어주고 기존 문자열에 다음 문자열을 하나 추가해서 alpha안에 새로 등록을 시켜주며, 만약 slice한 구간이 여러개일 경우 바깥 for문이 이미 result에 인덱스 값을 넣었는데 또 돌릴 이유가 없기 때문에 i의 값을 j-1한 값으로 재설정을 해준 뒤 break를 통해 안쪽 반복문을 나가준다.

(i의 값을 j가 아닌 j-1로 설정한건 다음 for문에 진입할때 i의 값을 +1 시키기 때문에 -1을 해줘서 값을 보존시키려고 적용시켰다.)

 

이렇게 반복문이 완료되고 나서 값을 리턴하게 되면 제대로 해결되는 것을 확인할 수 있다.