[JAVA 문제 풀이] 339. 압축

내가 작성한 코드

import java.util.*;

class Solution {
    public int[] solution(String msg) {
        Map<String, Integer> dictionary = new HashMap<>(); // 모든 문자열 담을 리스트
        List<Integer> answer = new ArrayList<>(); 

        // 사전 초기화 (A=1 ~ Z=26)
        for (int i = 0; i < 26; i++) {
            dictionary.put(String.valueOf((char) ('A' + i)), i + 1);
        }

        int dictIndex = 27; // 사전에 담는 문자열의 인덱스
        int i = 0;

        while (i < msg.length()) {
            String w = "" + msg.charAt(i);
            int j = i + 1;

            // 사전에 있는 가장 긴 현재 문자로 시작하는 단어(w) 찾기
            while (j <= msg.length()) {
                String next = msg.substring(i, j);
                if (dictionary.containsKey(next)) {
                    w = next;
                    j++;
                } else {
                    break;
                }
            }

            // w의 번호 저
            answer.add(dictionary.get(w));

            // 사전에 w + 다음 글자 등록
            if (j <= msg.length()) {
                String next = msg.substring(i, j);
                dictionary.put(next, dictIndex++);
            }

            // 다음 위치로 이동
            i += w.length();
        }

        return answer.stream().mapToInt(Integer::intValue).toArray();
    }
}

다른 사람의 코드

import java.util.*;

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++) {

            // 현재 위치 i부터 시작해, 사전에 있는 가장 긴 문자열을 찾기 위해
            // 사전을 역순으로 확인 (길이가 긴 문자열을 우선 매칭)
            for (int j = dic.size() - 1; j >= 0; j--) {

                // msg의 현재 위치 i부터 시작하는 부분 문자열이
                // 사전의 dic.get(j)로 시작하는지 확인
                if (msg.substring(i).startsWith(dic.get(j))) {

                    // 사전에 일치하는 문자열을 찾았으므로,
                    // 그 길이만큼 i를 증가시켜 다음 위치로 이동
                    i += dic.get(j).length() - 1;

                    // 해당 문자열의 사전 색인 번호 (1부터 시작이므로 j+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;
    }
}

LZW(Lempel-Ziv-Welch) 알고리즘 - stupefyee

기술정리

https://stupefyee.inblog.io/lzwlempelzivwelch-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98--60015?traffic_type=internal