[2018 KAKAO BLIND RECRUITMENT][3차] 압축 for JAVA

[문제 설명]

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

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

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

 

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

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

현재 입력(w)	다음 글자(c)	출력	사전 추가(w+c)
K	A	11	27:KA
A	K	1	28:AK
KA	O	27	29:KAO
O		15

 

[풀이] 

일단 사전의 길이가 가변하기 때문에 ArrayList를 활용했고, 단어를 하나씩 빼서 가져오기 때문에 Queue를 사용했다.

전체적으로 하나의 단어를 빼고, 비교하고, 추가하기 때문에 별 다른 라이브러리 없이 구현부는 while문, doWhile문을 사용해서 구현했다. 카카오 문제에서 제시하는 조건을 따라 차근차근 풀어보니 그렇게 어려운 문제는 아니였다. 

 

 

[코드]

public static int[] solution(String msg) {
        ArrayList<String> AL = new ArrayList<String>();                 // 길이가 동적이므로 arraylist
        ArrayList<Integer> answer = new ArrayList<Integer>();         // 리턴할 배열
        AL.add("0");                                                 // 1번째 인덱스로 시작하기 위하여
        char English = 'A';
        for (int i = 0; i < 26; i++) {                                  // 알파벳 사전 초기화
            AL.add(English++ + "");
        }
 
        Queue<Character> q = new LinkedList<>();
        for (int i = 0; i < msg.length(); i++) {                      // q에 msg단어를 하나씩 넣어줌
            q.add(msg.charAt(i));
        }
 
        while (!q.isEmpty()) {                                         //q가 비어있지 않다면
            String temp = q.remove() + "";                             //첫단어 ex) K
            String tempNext = "";                                     //첫단어 + 두번째 단어 ex)KA
            if (q.size() > 0) {
                tempNext = temp + q.peek();
            }
            boolean flag = false;                                     //만약 사전에 두번째 단어 이상까지 있다면 계속해서 문자열에 붙혀줘야 되기 때문에 반복조건을 정함.
            do {
                flag = false;
                if (AL.contains(temp)) {                             //1.첫 번째 단어가 있고
                    if (AL.contains(tempNext)) {                     //2.두번째 단어가 있다면
                        temp = temp + q.remove();                     //3.temp는 KA가 되고
                        tempNext = tempNext + q.peek();                 //4.tempNext는 KAO가 되어 반복함
                        flag = true;
                    } else {                                         //2.두번째 단어는 없다면
                        answer.add(AL.indexOf(temp));                 //3.temp의 인덱스를 출력하고
                        if (!tempNext.equals(""))                    
                            AL.add(tempNext);                          //4.사전에 새롭게등록한다..
                    }
 
                }
            } while (flag);
 
        }
 
        int[] result = new int[answer.size()];                         //int형 배열로 전환
        int size = 0;
        for (int temp : answer) {
            result[size++] = temp;
        }
        return result;
    }

 

프로그래머스에서 테스트케이스 통과

[느낀점]

알고리즘 공부를 다시 시작한지 두 세달 정도 되어 가는데 실력이 많이 늘은 것을 체감한다..

근데 아직도 좋은 코드? 라고는 생각이 안들고 생각하는 것을 그대로 코드화 시키는 수준인 것 같다고 생각한다.

이미 풀어 놓은 문제들도 많으니 시간 될 때마다 올리면서 다시 풀이방법을 상기시키는 시간을 가져야 겠다.