프로그래머스 코딩테스트 연습 - [3차] 압축 (2018 카카오 블라인드)

# 주소

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

프로그래머스

# 문제

문제 설명

압축

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

어피치는 여러 압축 알고리즘 중에서 성능이 좋고 구현이 간단한 LZW(Lempel–Ziv–Welch) 압축을 구현하기로 했다. LZW 압축은 1983년 발표된 알고리즘으로, 이미지 파일 포맷인 GIF 등 다양한 응용에서 사용되었다.

LZW 압축은 다음 과정을 거친다.

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

압축 알고리즘이 영문 대문자만 처리한다고 할 때, 사전은 다음과 같이 초기화된다. 사전의 색인 번호는 정수값으로 주어지며, 1부터 시작한다고 하자.

색인 번호123...242526

단어

A

B

C

...

X

Y

Z

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

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

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

K	A	11	27: KA
A	K	1	28: AK
KA	O	27	29: KAO
O		15

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

입력으로 TOBEORNOTTOBEORTOBEORNOT가 들어오면 다음과 같이 압축이 진행된다.

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

T	O	20	27: TO
O	B	15	28: OB
B	E	2	29: BE
E	O	5	30: EO
O	R	15	31: OR
R	N	18	32: RN
N	O	14	33: NO
O	T	15	34: OT
T	T	20	35: TT
TO	B	27	36: TOB
BE	O	29	37: BEO
OR	T	31	38: ORT
TOB	E	36	39: TOBE
EO	R	30	40: EOR
RN	O	32	41: RNO
OT		34

입력 형식

입력으로 영문 대문자로만 이뤄진 문자열 msg가 주어진다. msg의 길이는 1 글자 이상, 1000 글자 이하이다.

출력 형식

주어진 문자열을 압축한 후의 사전 색인 번호를 배열로 출력하라.

입출력 예제

msganswer

KAKAO	[11, 1, 27, 15]
TOBEORNOTTOBEORTOBEORNOT	[20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34]
ABABABABABABABAB	[1, 2, 27, 29, 28, 31, 30]

해설 보러가기

# 문제 해설 및 코드 리뷰

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

class Solution {
    public int[] solution(String msg) {
        HashMap<String, Integer> hashMap = new HashMap<>();
        String now = "A";
        char temp = 'A';
        for(int i = 1; i < 27; i++){
            hashMap.put(now, i);
            temp++;
            now = String.valueOf(temp);
        }
        now = "";
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0; i < msg.length() - 1; i++){
            now += msg.charAt(i);
            now += msg.charAt(i + 1);
            if(!hashMap.containsKey(now)){
                hashMap.put(now, hashMap.size() + 1);
                list.add(hashMap.get(now.substring(0, now.length() - 1)));
                now = "";
            }
            else{
                now = now.substring(0, now.length() - 1);
            }
        }
        now += msg.charAt(msg.length() - 1);
        if(hashMap.containsKey(now)){
            list.add(hashMap.get(now));
        }
        else{
            list.add(hashMap.size() + 1);
        }
        int[] answer = new int[list.size()];
        for(int i = 0; i < list.size(); i++)
            answer[i] = list.get(i);
        return answer;
    }
}

HashMap을 이용한 문자열 문제입니다.

카카오 문제라서 조금 쫄고 시작했는데 한시간 정도만에 풀 수 있었습니다.

차근차근 코드를 뜯어보며 살펴봅시다.

이 문제의 경우 의미를 잘 이해하는게 중요합니다.

문제의 요구사항은 첫째, 가장 긴 문자열을 찾고 없다면 사전에 해당 문자열을 넣고 초기화하기.

둘째, 사전에 존재하는 단어라면 그대로 배열에 넣고 다음 문자열 탐색입니다.

일단 문맥상으론 제가 설명하는 능력이 부족하여, 코드로 설명을 드리겠습니다.

HashMap<String, Integer> hashMap = new HashMap<>();
String now = "A";
char temp = 'A';
for(int i = 1; i < 27; i++){
    hashMap.put(now, i);
    temp++;
    now = String.valueOf(temp);
}

먼저 저는 HashMap을 사용하여 데이터 사전을 구축하였습니다.

문자열은 String타입으로, 그리고 해당 인덱스 값은 Integer로 저장해야 하기 때문입니다.

또한 A 부터 Z까지 사전을 미리 구축해야 하는데 총 26가지의 알파벳에 대해 1부터 26의 값을 삽입합니다.

now = "";
ArrayList<Integer> list = new ArrayList<>();
for(int i = 0; i < msg.length() - 1; i++){
    now += msg.charAt(i);
    now += msg.charAt(i + 1);
    if(!hashMap.containsKey(now)){
        hashMap.put(now, hashMap.size() + 1);
        list.add(hashMap.get(now.substring(0, now.length() - 1)));
        now = "";
    }
    else{
        now = now.substring(0, now.length() - 1);
    }
}

여기 코드부분이 제일 중요합니다.

ArrayList를 먼저 선언하는데 해당 자료구조는 정답을 담을 자료구조입니다. 중요한건 이 다음부터입니다.

for문을 msg.length - 1 만큼 반복합니다. msg.charAt(i + 1)을 쓸 것이기 때문입니다.

now에 msg.charAt(i)와 msg.charAt(i + 1)을 더했을 때 그 문자열이 hashMap에 포함되어 있지 않다면 hashMap에 삽입합니다.

hashMap의 크기는 hashMap의 크기 + 1만큼입니다.

그리고 정답을 담을 자료구조인 list에는 now의 끝부분을 자른 형태 (예를들면 "KAKAO예시에서 KA는 사전에 없으므로 KA에서 A를 자른, K의 값을 hashMap에서 찾아서 list에 담습니다)를 hashmap에서 찾아서 넣습니다.

그리고 now값은 초기화합니다.

그러나, 해당 값이 hashMap에 존재한다면(예를 들면 "KAKAO에서 KA도 없고 AK도 없었는데 그 다음 KA가 사전에 존재하기 때문에  hashMap도 존재합니다) now는 끝 부분을 자른 형태만 가지게 됩니다. (따라서 KA에서 A를 자른 K만 가져갑니다)

이렇게 된다면 그 다음 루프문에서 now는 A를 더하고 더불어서 그 다음 문자인 O도 더해지는 것입니다.

KAO도 역시 hashMap에 존재하지 않기 때문에 hashMap에 삽입 후 list에 담을 수 있는 것이지요.

now += msg.charAt(msg.length() - 1);
if(hashMap.containsKey(now)){
    list.add(hashMap.get(now));
}
else{
    list.add(hashMap.size() + 1);
}

이후, 마지막 문자에 대해서도 탐색을 해줘야하는데 now에 마지막 문자열을 더했을 때 그 문자열이 hashMap에 존재하면 list에 담고, 없으면 마찬가지로 hashMap에 삽입후 list에 값을 대입합니다. 

그러나 굳이 hashMap에 안넣고 list에 값만 넣어도 되기 때문에 전 값을 바로 넣겠습니다.

이후 answer배열을 만들어서 list의 모든 값을 대입 후 return하면 정답이 됩니다.

감사합니다.