압축

 

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

프로그래머스

 

Level 2 

 

주어진 알고리즘 설명을 토대로 문자열을 압축한 결과값을 반환해야하는 구현 문제.

 

특별한 알고리즘 없이도 해결 방법을 찾을 수 있고 구현하는 과정에서 약간 어려울 뿐 크게 어렵지 않다. 

 

 

필자의 경우 위와 같이 구현하였으며 마지막 키의 경우 더 이상 뒤에 나올 문자열이 없으므로 최종 문자열 인덱스 확인 후 큐에 추가하고 정답을 반환했다. 

 

Hash 개념을 알고 있으면 크게 어렵지 않은 문제, 단 효율성 케이스가 없어 조금 아쉽긴 하나 그냥 단순히 배열을 완전 탐색하여 인덱스를 찾는 것 보다 Hash 가 훨씬 구현하기도 편하고 깔끔하다. 

 

import java.util.*;

public class Solution {
    public int[] solution(String msg) { //압축
        Queue<Integer> LZWQueue = new LinkedList<Integer>(); //LWZ 숫자가 담길 큐
        HashMap<String, Integer> LZWMap = new HashMap<String, Integer>(); //LWZ 인덱스 맵
        for(int cnt = 0; cnt < 26; cnt++) { //알파벳 대문자 초기 데이터 입력
            String key = "" + (char) ('A' + cnt);
            LZWMap.put(key, cnt+1);
        }

        String key = "";
        int lastLZWIndex = 26; //마지막 인덱스 정보
        for(int idx = 0; idx < msg.length(); idx++){
            String tempKey = ""+msg.charAt(idx); //현재 1byte 문자열
            if(key.length() > 0 && !LZWMap.containsKey(key + tempKey)) { //지난 문자열 + 현재 문자열을 가지고 있는지 확인
                LZWQueue.add(LZWMap.get(key)); //가지고 있지 않을 경우 지난 문자열의 인덱스 값을 큐에 추가
                LZWMap.put(key + tempKey, ++lastLZWIndex); //새로 인덱스 추가
                key = ""; //새로운 문자열로 시작
            }
            key += tempKey; //현재 문자열 병합
        }
        if(LZWMap.containsKey(key)){ //최종키 인덱스 추가
           LZWQueue.add(LZWMap.get(key));
        }else{
            LZWQueue.add(lastLZWIndex+1);
        }
        int[] answer = new int[LZWQueue.size()];
        for(int idx = 0; idx < answer.length; idx++) answer[idx] = LZWQueue.poll();
        return answer; //큐의 데이터 그대로 복사 후 반환
    }
}