압축

문제

카카오 매칭 팀은 메시지 전송 효율을 높이기 위해 LZW(Lempel–Ziv–Welch) 압축 알고리즘을 구현하려고 합니다. LZW 알고리즘은 다음 과정을 거칩니다.

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

영문 대문자로만 이뤄진 문자열이 주어질 때, LZW 압축을 거친 후의 색인 번호 배열을 출력하는 프로그램을 작성하는 문제입니다.

• 입력: 영문 대문자로만 이뤄진 문자열 msg (길이 1 이상 1,000 이하)
• 출력: 주어진 문자열을 압축한 후의 사전 색인 번호를 담은 정수 배열

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

풀이: HashMap을 활용한 LZW 알고리즘 시뮬레이션

문제에서 요구하는 LZW 알고리즘의 명세(1~5단계)를 순서대로 충실하게 구현하는 시뮬레이션 풀이입니다. 사전을 관리하기 위해 검색 속도가 빠른 HashMap을 사용합니다.

• 사전 초기화: A부터 Z까지 길이가 1인 26개의 알파벳을 사전에 미리 등록합니다. (값은 1부터 26까지 부여)
• 가장 긴 문자열(s) 탐색:
  • 현재 위치(idx)에서 시작하여 문자열을 한 글자씩 더해가며(c) 사전에 존재하는지 확인합니다.
  • 사전에 존재한다면 탐색 문자열(s)을 확장하고 idx를 증가시킵니다.
  • 사전에 존재하지 않는 새로운 단어(s+c)를 만나는 순간, 사전에 등록하고 탐색을 중단(break)합니다.
• 출력: 탐색이 중단되었을 때, 지금까지 완성된 가장 긴 문자열 s의 색인 번호를 리스트에 추가합니다.
• 마지막 문자열 처리: 바깥쪽 while문 안에서 인덱스 증가 로직이 모두 안전하게 처리되므로, 문자열의 끝에 도달했을 때 별도의 예외 처리 없이 마지막 단어의 색인 번호까지 깔끔하게 리스트에 담깁니다.

코드

import java.util.*;

class Solution {
    public int[] solution(String msg) {
        Map<String, Integer> map = new HashMap<>();
        
        // 1. 길이가 1인 모든 단어를 포함하도록 사전을 초기화
        for (int i = 0; i < 26; i++) {
            char c = (char) ('A' + i);
            map.put(String.valueOf(c), i + 1);
        }
        
        int idx = 0;
        List<Integer> list = new ArrayList<>();
        
        while (idx < msg.length()) {
            String s = "";
            
            // 2. 현재 위치에서 가장 긴 일치하는 문자열 s를 찾음
            while (idx < msg.length()) {
                String c = String.valueOf(msg.charAt(idx));
                if (map.containsKey(s + c)) {
                    s += c;
                    idx++;
                } else {
                    // 4. 사전에 없는 글자를 만났을 때 사전에 등록
                    map.put(s + c, map.size() + 1);
                    break;
                }
            }
            
            // 3. s에 해당하는 사전의 색인 번호를 출력
            list.add(map.get(s));
        }
        
        int[] ans = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ans[i] = list.get(i);
        }
        
        return ans;
    }
}

알고리즘 분류

구현 (Implementation), 문자열 (String), 해시를 사용한 맵 (Hash Map)