Lv.2 : 압축

👉 문제링크

프로그래머스

---

---

🔸 문제 분석 🔸

• 압축 알고리즘인 LZW를 구현하는 문제이다.
• 알고리즘 설명에 따라 문자열 처리를 수행하는 문제이다.
• 알파벳 대문자만 입력으로 주어진다.

🔸 문제 풀이 🔸

• 색인되는 문자열들은 그 값을 리스트에 저장한다.
• 색인되지 않는 문자열을 새롭게 추가한다.
• 리스트의 값을 반환한다.

---

🔸 코드 🔸

import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;

class Solution {
    public int[] solution(String msg) {
        // 사전 초기화
        Map<String, Integer> map = new HashMap<>();

        for (int i = 0; i < 26; i++) {
            map.put((char)('A' + i) + "", i + 1);
        }

        // 인덱싱
        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < msg.length(); i++) {
            int len = 1;
            while (i + len <= msg.length() && map.containsKey(msg.substring(i, i + len))) {
                len++;
            }

            list.add(map.get(msg.substring(i, i + len - 1)));

            if (i + len <= msg.length())
                map.put(msg.substring(i, i + len), map.size() + 1);

            i += len - 2;
        }

        // 출력
        int[] answer = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            answer[i] = list.get(i);
        }
        return answer;
    }
}

🔸 코드 해석 🔸

• 알파벳 대문자 26개를 map에 저장해둔다.
• 색인되지 않을때 까지 부분 문자열을 늘려간다.
  • 마지막으로 색인된 값을 list에 저장한다.
  • 색인되지 않은 부분 문자열은 새롭게 색인에 추가한다.
  • 색인된 값 이후로 다시 부분 문자열을 계산한다.
• list에 저장된 값들을 반환한다.

---

🔸 end 🔸

• LZW라는 압축 알고리즘을 구현하는 문제여서, 문제 설명량을 보고 어렵지 않을까 했는데 생각보단 간단했다.
  • 최대길이 문자열을 구할 때, 문자열의 범위를 벗어나는 경우를 예외처리하지 않아서 디버깅이 필요했다.
• 2018 KAKAO RECRUITMENT의 2번 문제이고 정답률은 95.80%로 쉬운 난이도인 것 같다.
  • 다음은 공식 해설 내용이다. 

GIF 파일 등에서 실제로 쓰이는 LZW 알고리즘을 설명해주고, 구현하는 문제입니다. 실제로 쓰이는 알고리즘을 구현해보는 것이 어떠셨나요? 압축이라는 말만으로 얼핏 어려워 보이지만, 설명에 나온 의사코드Pseudocode를 그대로 따라서 구현만 하면 되는 문제로, 기초적인 문자열과 배열을 다룰 수 있다면 풀 수 있는 문제입니다.
이 문제의 정답률은 95.80%입니다. 가장 많은 지원자가 잘 풀어주셨습니다. 언어별로는 Java 언어 사용자들이 조금 어려워했습니다.