[210118] 압축- 2018 KAKAO BLIND RECRUITMENT

0. 문제유형 : 문자열 처리, 자료구조 활용

1. 문제이해

programmers.co.kr/learn/courses/30/lessons/17684

코딩테스트 연습 - [3차] 압축

(1) 주요 요구사항

: 전송 메시지를 LZW 압축한 결과를 출력

LZW(Lempel-Ziv-Welch) 압축

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

- (1번) 초기 사전의 상태

색인 번호	1	2	3	...	24	25	26
단어	A	B	C	...	X	Y	Z

 

- (EX) 입력이 KAKAO 인 경우

현재 입력(w)다음 글자(c)출력사전 추가(w+c)

현재 입력(w)	다음 글자(c)	출력	사전 추가(w+c)
K	A	11	27: KA
A	K	1	28: AK
KA	O	27	29: KAO
O		15

 

(2) 제약/주의 사항

- 입력 : 영문 대문자로만 이뤄진 문자열 msg (1글자 이상 1000글자 이하)

- 다음 글자(c) 판단 : 마지막 문자인 경우 null point error에 주의해야 한다.

 

 

 

 

2. 전략

(1) 사전 자료구조 : HashMap<String, Integer> 이용

- 초기 : key를 A-Z로, value를 1~26으로 반복문을 통해 넣음

HashMap<String, Integer> dictionary = new HashMap<>();
for(int i = 0; i < 26; i++){
    dictionary.put(Character.toString('A' + i), i+1);
}

(2) LZW 알고리즘 구현 : public int[] LZW(String msg, HashMap<String, Integer> dic)

- 기준 index : start, end로 사전에서 찾을 key 단위 지정

- 범위 제한 : start < size / start+1 <= end <= size

 

① 사전에 해당 key가 있을 때까지 end범위 늘리기

    > dic.containsKey(msg.substring(start, end)

② 출력 : 찾은 key 범위에 해당하는 value 

    > dic.get(msg.substring(start, end)

③ 단어 등록 : (찾은 key범위 + 1)를 key로 등록,  (마지막 value + 1)를 value로 등록

    > dic.put(msg.substring(start, end+1), index++)

 

 

 

 

 

3. 참고사항

(1) A~Z 등록하는 방법 : (char)(65 + i) 로 'A'의 ASCII 코드 값을 이용할 수 있다!

 

 

 

 

 

4. 코드

import java.util.HashMap;
import java.util.ArrayList;

class Solution {
    public int[] solution(String msg) {
        int[] answer = {};
        HashMap<String, Integer> dictionary = new HashMap<>();
        for(int i = 0; i < 26; i++){
            dictionary.put(Character.toString('A' + i), i+1);
        }
        answer = LZW(msg, dictionary);
        return answer;
    }
    
    public int[] LZW(String msg, HashMap<String, Integer> dic){
        int start = 0; int end = start+1;
        int size = msg.length();
        int index = 27;
        ArrayList<Integer> printed = new ArrayList<>();
        while(start < size){
            for(end = start+1; end <= size; end++){
                if(dic.containsKey(msg.substring(start, end))){
                    continue;
                }
                else    break;
            }
            end--;
            printed.add(dic.get(msg.substring(start, end)));
            if(end < size)  dic.put(msg.substring(start, end+1), index++);
            start = end;
        }
        int asize = printed.size();
        int[] answer = new int[asize];
        for(int i = 0; i < asize; i++){
            answer[i] = printed.get(i);
        }
        return answer;
    }
}