2018 KAKAO BLIND - 압축

1. 문제

코딩테스트 연습 - [3차] 압축

2. 접근

주어진 LZW압축 과정을 그대로 따라가면 되기 때문에 크게 어려운 점은 없었다.

색인번호와 단어가 짝을 이뤄서 저장되기 때문에 HashMap을 활용했다. contains도 O(1)로 빠르기도 하고..

만약 map에 포함되어 있지 않다면 map에 추가하고 포함되어있다면 그걸 그대로 사용했다.

3. 코드

import java.util.ArrayList;
import java.util.HashMap;
class Solution {
    public int[] solution(String msg) {

        HashMap<String, Integer> map = new HashMap<>();
        ArrayList<Integer> list = new ArrayList<>();
        int idx = 26;
        for(int i=0;i<26;i++){
            char ch = (char)('A'+i);
            map.put(ch+"",i+1);
        }

        StringBuilder sb = new StringBuilder();
        for(int j=0;j<msg.length();j++){
            sb.append(msg.charAt(j));
            if(!map.containsKey(sb.toString())){ // 포함안된게 나오는 순간
                map.put(sb.toString(),++idx); // 인덱스에 넣고

                sb.deleteCharAt(sb.length()-1); // 마지막자리 빼고
                list.add(map.get(sb.toString()));
                j--;
                sb = new StringBuilder();
            }
            if(j==msg.length()-1){
                list.add(map.get(sb.toString()));
            }
        }
        
        int[] answer = new int[list.size()];
        for(int i=0;i<list.size();i++){
            answer[i] = list.get(i);
        }
        
        return answer;
    }
}

 

4. 결과