문제

신입사원 어피치는 카카오톡으로 전송되는 메시지를 압축하여 전송 효율을 높이는 업무를 맡게 되었다. 메시지를 압축하더라도 전달되는 정보가 바뀌어서는 안 되므로, 압축 전의 정보를 완벽하게 복원 가능한 무손실 압축 알고리즘을 구현하기로 했다.

어피치는 여러 압축 알고리즘 중에서 성능이 좋고 구현이 간단한 LZW(Lempel–Ziv–Welch) 압축을 구현하기로 했다. LZW 압축은 1983년 발표된 알고리즘으로, 이미지 파일 포맷인 GIF 등 다양한 응용에서 사용되었다.

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

1. 길이가 1인 모든 단어를 포함하도록 사전을 초기화한다.
2. 사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다.
3. w에 해당하는 사전의 색인 번호를 출력하고, 입력에서 w를 제거한다.
4. 입력에서 처리되지 않은 다음 글자가 남아있다면(c), w+c에 해당하는 단어를 사전에 등록한다.
5. 단계 2로 돌아간다.

압축 알고리즘이 영문 대문자만 처리한다고 할 때, 사전은 다음과 같이 초기화된다. 사전의 색인 번호는 정수값으로 주어지며, 1부터 시작한다고 하자.

예를 들어 입력으로 KAKAO가 들어온다고 하자.

현재 사전에는 KAKAO의 첫 글자 K는 등록되어 있으나, 두 번째 글자까지인 KA는 없으므로, 첫 글자 K에 해당하는 색인 번호 11을 출력하고, 다음 글자인 A를 포함한 KA를 사전에 27 번째로 등록한다.
두 번째 글자 A는 사전에 있으나, 세 번째 글자까지인 AK는 사전에 없으므로, A의 색인 번호 1을 출력하고, AK를 사전에 28 번째로 등록한다.
세 번째 글자에서 시작하는 KA가 사전에 있으므로, KA에 해당하는 색인 번호 27을 출력하고, 다음 글자 O를 포함한 KAO를 29 번째로 등록한다.
마지막으로 처리되지 않은 글자 O에 해당하는 색인 번호 15를 출력한다.

이 과정을 거쳐 다섯 글자의 문장 KAKAO가 4개의 색인 번호 [11, 1, 27, 15]로 압축된다.

입력으로 TOBEORNOTTOBEORTOBEORNOT가 들어오면 다음과 같이 압축이 진행된다.

입력

입력으로 영문 대문자로만 이뤄진 문자열 msg가 주어진다. msg의 길이는 1 글자 이상, 1000 글자 이하이다.

출력

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

예제 입력

ABABABABABABABAB

예제 출력

[1, 2, 27, 29, 28, 31, 30]

내가 했던 풀이 방법

1. A부터 Z까지 사전순으로 정렬하여 dictionary 배열을 만든다.
2. dictionary를 index와 element를 이용해 Map으로 만들어준다. 이때, 배열의 index가 value, element가 key가 되도록 해준다. value는 index를 +1을 해준 값으로 해준다. (필요한 것은 index이므로 key 값이 value가 될 경우, index 값을 가져오기 불편해지기 때문에 바꾸어준다.)
3. key를 27로 초기화해준다. (key 변수는 다음 value로 들어올 값이다.)
4. msg 문자열을 처음부터 끝까지 반복하여 해당 index에 문자를 char에 저장해주고, index를 i+1로 초기화해준다. (index는 msg의 index를 의미한다.)
5. 현재 char에 다음 문자을 합친 문자가 dicitonary에 없을 때, answer에 char의 색인번호를 가져와 추가해준다. char에 다음 문자를 합친 문자를 dictionary에 key로 추가해준다. 추가될 때마다 key는 1씩 증가한다. index가 msg를 넘어서 경우, answer에 char의 색인번호를 가져와 추가해준다. (즉, 다음 문자가 합쳐진 문자를 dictionary에 추가하는 연산을 생략한다.) 해당 연산을 마친 뒤, 반복문을 탈출한다.
6. char와 다음 문자를 합친 문자가 dictionary에 있을 경우, char를 char와 다음 문자를 합친 문자로 바꿔주고, i를 1 증가시켜준다. (i를 1 증가시켜주는 이유는 kakao를 예시로 들었던 문제를 보면 알 수 있다. 세 번째 글자에서 시작하는 KA가 사전에 있으므로, KA에 해당하는 색인 번호 27을 출력하고, 다음 글자 O를 포함한 KAO를 29 번째로 등록한다. 이 부분을 보면 KA가 사전에 있어 KA를 출력해주었기 때문에 KA가 동시에 처리가 된 것이다. 그러므로 i를 증가시켜주지 않으면 KA를 처리한 뒤 A를 다시 처리하게 되기 때문에 i를 증가시켜주어야 한다.
7. 모든 문자열을 다 처리한 뒤 answer를 return 해준다.

코드

function solution(msg) {
    var answer = [];
    let dictionary = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"];
    dictionary = new Map(dictionary.map((item, index) => [item, index+1]));
    let key = 27;
    for(let i=0; i<msg.length; i++) {
        let char = msg.charAt(i);
        let index = i+1;
        while(true) {
            if (index >= msg.length || !dictionary.has(char + msg.charAt(index))) {
                answer.push(dictionary.get(char));
                if (index < msg.length) {
                    dictionary.set(char + msg.charAt(index), key++);
                }
                break;
            } else {
                char += msg.charAt(index++);
                i++;
            }
        }
    }
    return answer;
}

회고

프로그래머스 특 ) 문제는 굉장히 길고 어려워 보이나 그대로 구현하면 되기 때문에 문제가 길수록 쉬움. 해당 문제를 보고 오,,, 난해한데,,,? 생각했는데 막상 구현해보니 단순했다. 구현 방법 자체는 거의 바로 찾은 편. 그러나 msg의 index 부분을 놓쳐 무한반복을 하게 됐는데 이 부분을 캐치 못한 건 조금 아쉬웠다. 그리고 가장 아쉬운 건 영어를 사전순으로 정렬하는 과정에서 틀렸다는 점.. 자다 일어나서 비몽사몽으로 풀어서 그런가.. 오타가 있었다. 다행히 결과에서 딱 한 개씩만 틀렸고 (그것도 색인번호가 작아서 찾을 수 있었다.) 해당 색인번호를 확인하니 오타가 있었다..ㅎㅎ... 이런 실수를 하다니. 결과 출력을 유심히 안 봤으면 삽질할 뻔 했다.