[프로그래머스] 압축 / 2018 KAKAO BLIND RECRUITMENT(3차) - JAVA

🖇️ 문제 링크

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

신입사원 어피치는 카카오톡으로 전송되는 메시지를 압축하여 전송 효율을 높이는 업무를 맡게 되었다. 메시지를 압축하더라도 전달되는 정보가 바뀌어서는 안 되므로, 압축 전의 정보를 완벽하게 복원 가능한 무손실 압축 알고리즘을 구현하기로 했다. 어피치는 여러 압축 알고리즘 중에서 성능이 좋고 구현이 간단한 LZW(Lempel-Ziv-Welch) 압축을 구현하기로 했다. LZW 압축은 1983년 발표된 알고리즘으로, 이미지 파일 포맷인 GIF 등 다양한 응용에서 사용되었다.

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

 

---

📝 문제 분석

해시맵으로 사전을 생성합니다.

1. 'A' ~ 'Z'까지 먼저 사전을 초기화합니다.

2. 사전에서 현재 입력과 일치하는 가장 긴 문자열을 찾습니다. ( substring으로 인덱스를 하나씩 늘리며 탐색 )

3. 입력에서 처리되지 않은 다음 글자가 남아있다면, 지금까지 찾은 가장 긴 문자열에 다음 글자를 덧붙여 사전에 저장합니다.

 

 

---

⌨️ 코드

import java.util.*;

class Solution {
    public static int[] solution(String msg) {
        ArrayList<Integer> list = new ArrayList<>();
        HashMap<String, Integer> map = new HashMap<>();
        // A - Z까지 init
        for(int i = 0; i < 26; i++)
            map.put((char)('A' + i) + "", i + 1);

        for(int i = 0; i < msg.length();) {
            // map에 있는 가장 긴 값을 구하자
            int end = i + 1;
            while(end <= msg.length()) {
                String sub = msg.substring(i, end);
                if(map.containsKey(sub)) {
                    end++;
                }
                else {
                    list.add(map.get(msg.substring(i, end - 1)));
                    map.put(sub, map.size() + 1);
                    break;
                }
            }
            if(end > msg.length())
                list.add(map.get(msg.substring(i, end - 1)));
            
            i = end - 1;
        }

        int[] ans = new int[list.size()];
        for(int i = 0; i < list.size(); i++)
            ans[i] = list.get(i);

        return ans;
    }
}

 

 

 

 

Uploaded by Notion2Tistory v1.1.0