[PROGRAMMERS] 압축 - JAVA

1. 문제

프로그래머스

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

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

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

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

 

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

---

2. 풀이

Map 초기화

key가 색인 문자열(String), value가 색인 번호(Integer)인 HashMap을 클래스 내에 선언한다.

init 메서드에서는 A부터 Z까지 사전을 초기화한다. 

    Map<String, Integer> dict = new HashMap<>();
    private void init(){
        for(int i='A';i<='Z';i++){
            dict.put(String.valueOf((char)i), i-'A'+1);
        }
    }

 

ArrayList -> int[] 변환

결과값을 맞는 타입으로 반환하기 위한 메서드다. ArrayList에 있는 요소를 하나씩 int[]에 담은 후 리턴한다.

    private int[] convert(ArrayList<Integer> list){
        int[] result = new int[list.size()];
        for(int i=0;i<result.length;i++){
            result[i] = list.get(i);
        }
        
        return result;
    }

 

Main

0.  init메서드를 실행시켜 dict(HashMap)을 초기화한다.

1.  현재의 msg 길이를 len에 저장한다.

2.  msg 끝에 더미 문자열 '.'을 추가한다. 추가하는 이유는 뒤에서 substring을 사용하기 때문이다. substring은 start idx ~ end idx까지 문자열을 자르는 메서드인데, end idx를 포함하지 않아 msg를 그대로 사용하면 예외상황이 너무 많이 발생한다. 따라서 더미 문자열을 추가해 이 상황을 방지한다.

3.  i는 시작문자 인덱스, j는 끝문자+1 인덱스다. i부터 j까지 substring을 이용해 자른 후, 그 값을 sub에 저장한다.

4.  dict(HashMap)에 sub가 있다면

4-1.  list(결과값저장 리스트)에 색인번호를 더한다.

4-2.  dict에 sub+다음문자열1개를 key로, 현재 dict 사이즈 +1을 value로 해서 put한다. value가 dict사이즈 +1인 이유는 색인 번호가 추가된 순으로 하나씩 늘어나기 때문이다. 어떤 조건 체크도 없이 바로 추가하는 이유는 j가 len부터 시작해서 i까지 역순으로 탐색하기 때문이다. 따라서 key인 (sub+다음문자열1개)는 항상 dict에 없는 값이다.

4-3.  바깥 for문에서 반복을 실행할 때마다 i++을 하기 때문에 다음 반복에서 i가 j부터 시작할 수 있도록 j-1값을 저장한다.

5.  반복이 끝났다면 convert 메서드를 이용해 list를 변환 후 반환한다.

    public int[] solution(String msg) {
        init();
        int len = msg.length();
        msg += '.';//더미문자열추가
        ArrayList<Integer> list = new ArrayList<>();


        String sub;
        for(int i=0;i<len;i++){
            for(int j=len;j>i;j--){
                sub = msg.substring(i,j); 
                
                if(dict.containsKey(sub)){
                    list.add(dict.get(sub));
                    dict.put(sub+msg.charAt(j), dict.size()+1);
                    i = j-1;
                    break;
                }
            }
            
        }
        
        return convert(list);
    }

 

전체 코드

import java.util.*;

class Solution {
    Map<String, Integer> dict = new HashMap<>();
    public int[] solution(String msg) {
        init();
        
        int len = msg.length();
        msg += '.';//더미문자열추가
        ArrayList<Integer> list = new ArrayList<>();

        String sub;
        for(int i=0;i<len;i++){
            for(int j=len;j>i;j--){
                sub = msg.substring(i,j); 
                
                if(dict.containsKey(sub)){
                    list.add(dict.get(sub));
                    dict.put(sub+msg.charAt(j), dict.size()+1);
                    i = j-1;
                    break;
                }
            }
            
        }
        
        return convert(list);
    }
       
    private void init(){
        for(int i='A';i<='Z';i++){
            dict.put(String.valueOf((char)i), i-'A'+1);
        }
    }
    
    private int[] convert(ArrayList<Integer> list){
        int[] result = new int[list.size()];
        for(int i=0;i<result.length;i++){
            result[i] = list.get(i);
        }
        
        return result;
    }
}

---

3. 결과

이제 다시 꾸준히 풀기 시작해야겠다!