[프로그래머스 코딩테스트] 압축

신입사원 어피치는 카카오톡으로 전송되는 메시지를 압축하여 전송 효율을 높이는 업무를 맡게 되었다. 메시지를 압축하더라도 전달되는 정보가 바뀌어서는 안 되므로, 압축 전의 정보를 완벽하게 복원 가능한 무손실 압축 알고리즘을 구현하기로 했다.

예제

예를 들어 입력으로 KAKAO가 들어온다고 하자.

현재 사전에는 KAKAO의 첫 글자 K는 등록되어 있으나, 두 번째 글자까지인 KA는 없으므로, 첫 글자 K에 해당하는 색인 번호 11을 출력하고, 다음 글자인 A를 포함한 KA를 사전에 27 번째로 등록한다.
두 번째 글자 A는 사전에 있으나, 세 번째 글자까지인 AK는 사전에 없으므로, A의 색인 번호 1을 출력하고, AK를 사전에 28 번째로 등록한다.
세 번째 글자에서 시작하는 KA가 사전에 있으므로, KA에 해당하는 색인 번호 27을 출력하고, 다음 글자 O를 포함한 KAO를 29 번째로 등록한다.
마지막으로 처리되지 않은 글자 O에 해당하는 색인 번호 15를 출력한다.

이 과정을 거쳐 다섯 글자의 문장 KAKAO가 4개의 색인 번호 [11, 1, 27, 15]로 압축된다.

풀이

문제를 풀기 위해선 첫번째로, 사전을 만들어야하고 두번째로는 현재 문자열을 저장하는 변수와 다음 문자를 고려해 사전에 추가할 문자열을 저장할 변수가 필요하다.
사전을 만들때 ArrayList를 사용해서 만들어도 되지만 속도 측면에서 HashMap이 더 뛰어나기에 HashMap을 사용해 만들어준다.

코드

import java.util.*;

class Solution {
    public ArrayList<Integer> solution(String msg) {
        HashMap<String, Integer> map = new HashMap<>(); //사전
        
        for(int i=0; i<26; i++){
            map.put(String.valueOf((char)('A' + i)), i+1); //알파벳 먼저 넣음
        }
        
        ArrayList<Integer> answer = new ArrayList<>();
        int idx=0;
        
        while(idx+1 < msg.length()){
            String str = ""; //현재 문자열
            String pre = String.valueOf(msg.charAt(idx)); //이전 문자열
            
            for(int i=1; i+idx <= msg.length(); i++){
                str = msg.substring(idx, idx+i);
                if(!map.containsKey(str)){ //사전에 해당 문자열을 가지고 있지 않다면
                    map.put(str, map.size()+1);
                    break;
                }
                pre = str; //이전 문자열 현재 문자열로 초기화
            }
            answer.add(map.get(pre)); //이전 문자열번호 출력
            idx += pre.length(); //이전 문자열 길이만큼 idx 번호 증가
        }
        
        if(idx == msg.length()-1){ //마지막 번호이면
            answer.add(map.get(String.valueOf(msg.charAt(idx))));
        }
        
        
        return answer;
    }
}