[2018 카카오 블라인드] 압축 (JAVA)

문제

---

풀이

• dict: String을 key로, 인덱스를 value로 갖는 HashMap
• longestWordLength는 dict의 key 중 가장 긴 길이값

1. initDict(): A부터 Z까지 초기화한다.

2. LZW(): LZW 알고리즘에 따라 주어진 msg를 압축한다.

   a. msg를 처음부터 끝까지 탐색한다.
   b. getAvailableWordLength(): 주어진 index부터 시작하는 substring 중 사전에 존재하는 가장 긴 단어의 길이를 구한다.

   • longestWordLength부터 하나씩 줄여가며 그 substring이 dict에 존재하는지 확인한다.

   c. 알아낸 current의 사전 인덱스를 dict에서 찾아 result에 저장한다.
   d. 만약 current의 다음 글자가 존재한다면

   • current와 다음 글자를 합친 next를 dict에 새로 저장한다.
   • longestWordLength를 최댓값으로 갱신한다.

---

코드

import java.util.*;

class Solution {
    
    private static final int ALPHABET = 64;

    private Map<String, Integer> dict;
    private int longestWordLength;

    public int[] solution(String msg) {
        initDict();
        return LZW(msg);
    }

    private void initDict() {
        dict = new HashMap<>();
        for (char i = 'A'; i <= 'Z'; i++) dict.put(i + "", i - ALPHABET);
        longestWordLength = 1;
    }

    private int[] LZW(String msg) {
        List<Integer> result = new ArrayList<>();
        String current, next;
        int index = 0;
        while (index < msg.length()) {
            int length = getAvailableWordLength(msg, index);
            current = msg.substring(index, index + length);
            result.add(dict.get(current));
            if (index + length < msg.length()) {
                next = msg.charAt(index + length) + "";
                dict.put(current + next, dict.size() + 1);
                longestWordLength = Math.max(longestWordLength, length + 1);
            }
            index += length;
        }
        return result.stream().mapToInt(Integer::valueOf).toArray();
    }

    private int getAvailableWordLength(String msg, int startIndex) {
        int length = longestWordLength;
        while (length > 1) {
            int endIndex = startIndex + length;
            if (endIndex - 1 < msg.length()) {
                String word = msg.substring(startIndex, endIndex);
                if (dict.containsKey(word)) break;
            }
            length--;
        }
        return length;
    }
}