압축

Posted on Edited on In , ,

문제정의

LZW압축을 구현하는 문제이다. 압축 알고리즘에 대한 상세한 설명은 아래 링크에서 확인하고 오길 바란다.

문제 링크

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.ArrayList;
import java.util.HashMap;

public class Compress {

    //프로그래머스 문제풀이 level2 압축
    public static void main(String[] args) {
        String msg = "KAKAO";
        ArrayList<Integer> answer = new ArrayList<>();
        HashMap<String, Integer> map = new HashMap<>();
        for(int i = 0; i < 26; i++)
            map.put(String.valueOf((char)('A'+i)), i+1);
        
        int w = 0;
        int c = 1;
        boolean flag = false;
        while(c <= msg.length())
        {
            int value = map.getOrDefault(msg.substring(w,c), 0);
            while(value != 0)
            {      
                c++;
                if(c > msg.length())
                {
                    flag = true;
                    break; 
                }
                   
                value = map.getOrDefault(msg.substring(w,c), 0);
                
            }
            answer.add(map.get(msg.substring(w, c-1)));
            if(flag)
                c--;
            map.put(msg.substring(w, c), map.size()+1);
            w = c-1;
            if(flag)
                break;
            
        }
    }
    
}
사전을 map으로 구현하였다. 일단 A부터 Z까지 기본 단어를 만들어 놓는다. 그리고 w에서 c까지의 문자열을 반복해서 본다. c의 값을 늘려가며 처음으로 map에 없는 단어가 나올 경우 맵에 해당 문자열을 저장하고 바로 직전 반복의 문자열은 색인 값을 반환한다. 그리고 w에 다음 위치인 c-1을 집어넣으면 되는 단순한 알고리즘이다. 하지만 이 반복은 c가 메시지의 길이에 달했을 때 배열범위에 문제가 생기므로 이에 대한 처리를 따로 해야한다. flag와 관련된 부분이 그 부분이다.

최종 시간복잡도는 \(O(n)\)이다.

테스트



flag관련된 함수를 없앨 수 있는지 고민해봐야겠다. 깔끔하지 않다.