Implementation(String)-[3차]압축

❔ 문제

카카오 lv2. [3차]압축

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

💡 핵심 아이디어

LZW(Lempel-Ziv-Welch) 압축 구현

문자열 가공 문제이며, 문제에 정확하고 구체적인 처리 순서, 방법이 나타나있다.

따라서 이런 문제는 ‘구현’문제로 분류해야한다.

"LZW 압축은 다음 과정을 거친다."

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

=> 구현

사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다.

<-> 해당 검색 키워드와 일치하는 값이 있으면, 해당 index 저장 후 다음 글자 합치기

다음 합친 글자도 일치값이 있으면 index 갱신

만약 없으면, 기존 index값 답에 add & 해당 합친 글자 값으로 사전에 추가

검색 단어 다음 글자로 초기화

문자열 끝에 도달하면 반복 종료

🌊 로직

1. 사전 초기화 : A~Z까지 <문자, index> 형태로 ‘사전(Map)’을 초기화 한다.
2. 반복 : 위와 같은 방법으로 사전을 갱신하며 만족하는 index값을 동적배열에 추가한다.
3. 답 반환 : 동적배열을 답 형식인 정적배열로 변환해 반환한다.

✅ 코드

최악의 경우 O(N) : O(msg.length()) = O(1000)

일치하는 key값이 한글자 단위로만 있는 경우 해당 문자열의 길이만큼 한글자씩 사전을 갱신(O(1))한다

import java.util.*; 
class Solution {
    public int[] solution(String msg) {
        /*
        초기화 (1번)
        */
        HashMap<String, Integer> map = new HashMap<>() ; 
        int i ; 
        for(i = 0; i <= 26; i++){ // O(26)
            String key = (char)(i+64) +"" ; 
            map.put(key, i) ; 
        }
        
        
        /*
        반복 (2~4번)
        */
        ArrayList<Integer> list = new ArrayList<>() ; 
      
        int index = 0 ;
        String search = "" ; 
        for(int j = 0 ; j < msg.length() ; j++){ // 최악의 경우 O(msg.length())
            search += msg.charAt(j) ; 
            if(map.containsKey(search)){
                index = map.get(search) ; 
            }else{
                list.add(index) ; 
                map.put(search, i++) ;
                search = "" ; 
                j--;
            }
        }
        if(search!="")
            list.add(index) ; 
        
        /*
        답 반환 : list -> array
        */
        int[] answer = new int[list.size()] ; 
        for(int k = 0 ; k < list.size() ; k++){ // 최악의 경우 O(msg.length())
            answer[k] = list.get(k) ; 
        }
        return answer ; 
    }
}