[프로그래머스] Lv.2 [3차] 압축 (Java)

문제

풀이

import java.util.*;
class Solution {
    public int[] solution(String msg) {
        HashMap<String,Integer> hm = new HashMap<>();
        // <문자열,색인번호> 
        ArrayList<Integer> zipped = new ArrayList<>();
        // 압축 결과인 색인번호 리스트
        for(char c='A';c<='Z';c++) {
            hm.put(String.valueOf(c),c-'A'+1);
        }
        // 기본 사전 초기화
        int idx = 27;
        while(!msg.isEmpty()) {
            String w="";
            int i=1;
            for(;i<=msg.length();i++) {
                if(hm.containsKey(msg.substring(0,i))) {
                    w = msg.substring(0,i);
                }else {
                    hm.put(msg.substring(0,i),idx++);
                    break;
                }
            }
            zipped.add(hm.get(w));
            msg = msg.substring(i-1);
        }
        
        int[] answer = new int[zipped.size()];
        for(int i=0;i<answer.length;i++) {
            answer[i] = zipped.get(i);
        }
        return answer;
    }
}

• int idx : 사전에 넣을 때 쓰일 색인 번호. 현재 26까지 들어가있으므로 27부터 시작

while 문이 사전에서 현재 입력과 일치하는 가장 긴 w를 찾는 과정이다.

1. w는 길이가 1인 문자열부터 시작한다.
   -ex. msg="KAKAO"인 경우 w="K"부터 시작됨
2. 현재 길이+1인 문자열이 사전에 존재한다면, 그 문자열을 w로 바꾼다.
3. 현재 길이+1인 문자열이 사전에 존재하지 않는다면, 그 문자열을 사전에 등록하고 w의 색인 번호를 정답에 추가한다.
4. 정답에 추가한 문자열을 입력에서 삭제한다.
5. 모든 문자열을 정답에 추가할 때까지 1~4 단계를 반복한다.