[프로그래머스/Java] 압축

문제

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

프로그래머스

LZW는 데이터를 압축하는 알고리즘이다. LZW는 다음과 같은 과정을 거쳐서 압축한다.

1. 길이가 1인 모든 단어를 포함하여 사전을 초기화한다.
2. 사전에서 현재 입력과 일치하는 가장 긴 문자열 `w`를 찾는다.
3. `w`에 해당하는 사전의 인덱스를 출력하고, 입력에서 `w`를 제거한다.
4. 입력에서 처리되지 않은 다음 글자(`c`)가 남아있다면 `w+c`를 사전에 등록한다.
5. 2단계로 돌아간다.

문제에서는 영문 대문자만 처리한다. 때문에 사전은 A~Z로 초기화 되어있다.

문자열 `msg`이 주어지면 LZW 알고리즘을 적용한 사전 인덱스 출력 결과를 반환해야 한다.

 

풀이

사전을 A~Z로 초기화하는 방법에서 조금 헤맸는데, 앞으로는 `(char) ('A' + i)`를 반복해서 넣어주는 방식을 사용해야겠다.

항상 문제를 제대로 읽어야 한다고 느끼는데, 이번에도 인덱스가 중복을 허용하지 않는 줄 착각하고, Set을 사용하려다 계속 실패했다. 

💡Java에서 입력 순서가 보장되는 Set은 `LinkedHashSet` 구현체다.

 

처음에는 이중 for문을 사용해서 `j`를 늘려가며 인덱싱해보려 시도했으나 도중에 꼬이는 바람에 실패했다. 그래서 정돈된 코드를 찾아서 풀었다. 아직 인덱싱하는 방법에 서툰 것 같아 인덱싱 시뮬레이션을 많이 해봐야겠다고 느꼈다.

 

⚠`substring` 메서드의 두 번째 인자는 해당 인덱스는 포함하지 않으니 주의할 것.

 

코드

import java.util.*;

class Solution {
    public List<Integer> solution(String msg) {
        // 인덱스 초기화
        List<String> dictionary = new ArrayList<>();
        dictionary.add("");
        for (int i = 0; i < 26; i++) {
            dictionary.add(String.valueOf((char) ('A' + i)));
        }
        
        List<Integer> index = new ArrayList<>();
        int start = 0;
        while (start < msg.length()) {
            int end = start + 1;
            // 사전에 없는 단어가 나올 때까지 문자열 길이를 늘려가며 탐색
            while (end <= msg.length() && dictionary.contains(msg.substring(start, end))) {
                end++;
            }
            
            // 사전에 있는 현재 단어까지 인덱스에 추가
            String w = msg.substring(start, end - 1);
            index.add(dictionary.indexOf(w));
            
            // 다음 글자를 추가하여 사전에 추가
            if (end <= msg.length()) {
                String wc = msg.substring(start, end);
                dictionary.add(wc);
            }
            
            start = end - 1;
        }
                    
        return index;
    }
}