(2018카카오) 압축 LZW 알고리즘 Java

 

https://programmers.co.kr/learn/courses/30/lessons/17684

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

 

String 문자열 탐색 기반 문제이다.

 

dictionary를 map으로 만들어서 실행한다. 

Ascii코드의 알파벳 대문자 값을 이용하여 dictionary를 생성했다.

 

아래는 필자의 코드이다.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] solution(String msg) {
        ArrayList<Integer> list = new ArrayList<>();

        int num = 1;//add index
        Map<String, Integer> map = new HashMap<>();

        //dic 생성
        for (int i = 65; i <= 90; i++) {
            String c = String.valueOf((char) i);
            map.put(c, num++);//1~26
        }
        
        //msg 탐색
        for (int i = 0; i < msg.length(); ) {
            int j = msg.length() - i;
            while (!map.containsKey(msg.substring(i, i + j))) {//사전에 있으면 break
                j--;//가장 긴것부터 탐색 KAKAO KAKA KAK KA K
                if (j == 0) {
                    break;
                }
            }

            if (i + j == msg.length()) {//끝자리 문자열인 경우
                String s = msg.substring(i, i + j);
                list.add(map.get(s));
                map.put(s, num++);
            } else {//끝자리 문자열이 아닌 경우
                String s = msg.substring(i, i + j + 1);
                list.add(map.get(s.substring(0, s.length() - 1)));
                map.put(s, num++);
            }
            i += j;
        }
        
        //list to array
        int[] answer = new int[list.size()];
        for (int i = 0; i < answer.length; i++) {
            answer[i] = list.get(i);
        }

        return answer;
    }
}

 

HashMap을 이용 : String값으로 Key에 문자열을 넣고, Integer값으로 index를 Value에 저장한다.

 

map에 해당 Key가 있는지를 containsKey를 이용하여 문자열을 길게 우선하여 잘라서 탐색한다.

substring 메소드를 이용하여 문자열을 자르는데 사용한다.

 

그리고 list에 출력할 index값은 다음과 같이 추출한다.

map에서 get할 index는 위에서 만든 "길게 자른 문자열"에서 한글자를 빼서 얻는다.

 

 

---

 

아래는 다른 사람의 코드인데, 필자의 코드가 조금 더 길지만 효율성 측면에서 더 우수하다.

import java.util.ArrayList;

class Solution {
  public int[] solution(String msg) {
    ArrayList<String> dic = new ArrayList<String>();
    ArrayList<Integer> result = new ArrayList<Integer>();

    for(int i = 0 ; i < 26; i++) {
        dic.add(String.valueOf((char)('A'+i)));
    }

    for(int i = 0 ; i < msg.length() ; i++) {
        for(int j = dic.size()-1 ; j >= 0 ; j--) {
            if(msg.substring(i).startsWith(dic.get(j))) {
                i += dic.get(j).length()-1;
                result.add(j+1);
                if(i+1 < msg.length())
                    dic.add(dic.get(j)+msg.charAt(i+1));
                break;
            }
        }
    }

    int[] answer = new int[result.size()];

    for(int i = 0 ; i < result.size() ; i++) 
        answer[i] = result.get(i);

    return answer;  
  }
}