프로그래머스 LV2. 압축 (자바)

🍀 문제

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를 출력한다.

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

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

 

입력 형식

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

출력 형식

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

입출력 예제

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]

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

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

 

😊 나의 코드

import java.util.*;
class Solution {
    public int[] solution(String msg) {
        HashMap<String, Integer> map = new HashMap<String, Integer>(); //사전 (key:단어/value:인덱스) 
		ArrayList<Integer> list = new ArrayList<Integer>();

		int index = 1;// 색인 번호
		for (int i = 65; i <= 90; i++) { //A~Z 사전에 초기화
			map.put(Character.toString((char) i), index++);
		}

		String str = "";
		for (int i = 0; i < msg.length(); i++) {
			str += msg.charAt(i);
			if (!map.containsKey(str)) { //사전에 없는 단어면
				map.put(str, index++); //사전에 등록
                // 이전 단어 색인번호 출력
				list.add(map.get(str.substring(0, str.length() - 1))); 
				i = i - 1;
				str = "";
			}
		}
		list.add(map.get(str));

		int[] answer = new int[list.size()];
		for (int i = 0; i < list.size(); i++) {
			System.out.print(list.get(i) + ", ");
			answer[i] = list.get(i);
		}

		return answer;
    }
}

 

사전에 등록될 단어들을 HashMap을 사용하여 저장했다.

(key는 단어고 value는 인덱스)

 

이 map을 통해 특정 단어가 사전에 있는지를 확인했다.( map.contains(특정단어) )