[프로그래머스] [3차] 압축

코드 힌트

1. 사전 초기화:
   • 처음에는 단일 문자(알파벳 A부터 Z까지)로 초기화된 사전을 사용합니다. 이 사전은 문자열을 인코딩하는 데 사용됩니다.
2. 문자열 탐색:
   • 주어진 문자열을 탐색하면서 가능한 한 많은 문자들을 포함한 단어를 사전에서 찾습니다. 현재 문자부터 시작하여 다음 문자를 추가하면서 사전에 있는지 확인합니다.
3. 단어 추가 및 인덱스 기록:
   • 찾은 단어가 사전에 존재하지 않으면, 현재 단어의 인덱스를 결과 리스트에 추가합니다. 그 후, 다음 문자를 추가하여 새로운 단어를 사전에 추가합니다.
4. 문자열 인코딩:
   • 현재 탐색 위치가 문자열의 끝에 도달할 때까지 위의 과정을 반복하여 모든 단어를 인코딩합니다.
5. 결과 배열 변환:
   • 최종적으로 저장된 인덱스들을 배열로 변환하여 반환합니다.

 

사전 초기화 코드

String[] initialWords = {"", "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"};

 

---

정답은 더보기 클릭

import java.util.*;

class Solution {
    public int[] solution(String msg) {
        // 초기 사전 단어 목록을 생성 (A부터 Z까지)
        String[] initialWords = {"", "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"};
        
        // 입력 문자열의 길이
        int n = msg.length();
        // 현재 탐색 위치를 나타내는 인덱스
        int s = 0;
        
        // 사전 초기화 (List로 사용)
        List<String> dic = new ArrayList<>(Arrays.asList(initialWords));
        // 결과로 반환할 인덱스를 저장할 리스트
        List<Integer> list = new ArrayList<>();
        
        // 탐색 위치가 문자열 길이보다 작을 때까지 반복
        while (s < n) {
            StringBuilder currentWord = new StringBuilder();
            // 현재 문자를 추가하여 단어를 구성
            currentWord.append(msg.charAt(s));
            
            // 사전에 현재 단어와 다음 문자를 추가한 단어가 있을 때까지 반복
            while (s + 1 < n && dic.contains(currentWord.toString() + msg.charAt(s + 1))) {
                s++;
                currentWord.append(msg.charAt(s));
            }
            
            // 현재 단어의 인덱스를 리스트에 추가
            list.add(dic.indexOf(currentWord.toString()));
            
            // 다음 문자를 추가하여 새로운 단어를 사전에 추가
            if (s + 1 < n) {
                dic.add(currentWord.toString() + msg.charAt(s + 1));
            }
            
            // 탐색 위치를 다음으로 이동
            s++;
        }
        
        // 결과 리스트를 배열로 변환하여 반환
        int[] result = new int[list.size()];
        for (int i = 0; i < result.length; i++) {
            result[i] = list.get(i);
        }
        return result;
    }
}