카카오 신입공채 3차 코딩테스트 문제2 LWZ압축 JAVA 예제

카카오 신입공채 3차 코딩테스트 문제2 LWZ압축 JAVA 예제

---

카카오 신입공채 3차 코딩테스트의 2번문제는 실제 압축에 사용되는 LWZ 압축알고리즘에 대한 구현을 물어보는 문제 입니다. 문제에 대한 기본 설명은 다음과 같습니다. 

아래는 간단한 테스트 케이스 "KAKAO" 에 대한 압축 과정의 설명입니다. 

입력형식, 출력형식, 테스트 케이스는 다음과 같습니다.

전문보기 : http://tech.kakao.com/2017/11/14/kakao-blind-recruitment-round-3/

LZW 압축 JAVA 예제

---

데이터 사전 구현을 위해서 HashMap(dicMap)을 선언후 기초 데이터인 'A'~'Z'를 담아 주었습니다. 그 이후는 LZW알고리즘에 맞게 KEY를 검사후 존재 여부에 따라서 다음키와 조합하여 사전추가를 하여 문제를 풀이하였습니다.

/**
 * LZW 예제 
 */
public static ArrayList<String> solution(String str) {
    // 사전으로 사용할 맵을 생성하고 기초데이터를 입력
    HashMap dicMap = new HashMap<String, String>();
    char c = 'A';
    int n = 1;
    while(dicMap.size() < 26) {
        dicMap.put(String.valueOf(c++), String.valueOf(n++));
    } 
    
    // 메인소스
    ArrayList<String> retList = new ArrayList<String>();
    while(!str.isEmpty()) {
        for(int i = str.length(); i > 0; i--) {
            if(dicMap.containsKey(str.substring(0,i))){
                String key = str.substring(0, i);
                String nextKey = str.length() > i+1 ? str.substring(i, i+1) : "";
                retList.add(dicMap.get(key));
                if(!nextKey.isEmpty() && !dicMap.containsKey(key+nextKey)) { 
                    dicMap.put(key+nextKey, String.valueOf(dicMap.size()+1));
                }
                str = str.substring(key.length());
                break;
            }
        }
    }
    return retList;
}