[java] 프로그래머스 - 압축

문제

프로그래머스-압축
입력받은 문자열을 간단한 LZW(Lempel–Ziv–Welch) 압축과정을 통해 사전 색인 번호를 배열로 출력하는 문제.

• 제한 사항
  문자열 msg는 1 글자 이상, 1000 글자 이하이다

• 예시
  사전의 초기화는 A-1 … Z-26 으로 다음과 같다

A	B	C	…	X	Y	Z
1	2	3	…	24	25	26

KAKAO를 입력받은 경우,

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

출력 : [11, 1, 27, 15]

풀이

문제에서 주어지는 압축과정을 그대로 따르면 되는 문제다

• 과정

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

  가장 긴 문자열 w를 찾을 때, 현재 가지고있는 문자열 str에서 range를 정했다
  range는 Math.min(문자열 str의 길이, 사전에서 가장 긴 단어의 길이)로 두었다

str에서 range까지 문자열을 잘라서 사전에 있는지 보고, 없으면 range를 줄여가는 방식으로 w를 찾았다

소스코드

import java.util.*;
class Solution {
Map<String, Integer> map = new HashMap<>();
	static ArrayList<Integer> answer = new ArrayList<>();
	static String string;
	static int mapIdx; // 사전에 넣을 인덱스
	static int maxLen; // 사전에서 가장 긴 길이

	public int[] solution(String msg) {
		map.clear();
		answer.clear();
		string = msg;
		mapIdx = 27;
		maxLen = 1;
		for (int i = 1; i < 27; i++) {
			map.put((char) (65 + i - 1) + "", i); // 사전 초기화 A~Z
		}

		// 값 찾자
		getLZW(string);
		
		int[] ans = new int[answer.size()];
		for (int i = 0; i < ans.length; i++) {
			ans[i] = answer.get(i);
		}
//		System.out.println(map);
		return ans;
	}

	private void getLZW(String str) {
		if (str.equals("") || str == null)
			return;
		// 현재 str에서 0부터 가장 길고 맵에 있는 값을 찾는다 : W
		String w = str.substring(0, 1);
		int widx = 0;
		int range = Math.min(maxLen, str.length());
		for (int i = range; i > 1; i--) { // 큰 길이부터 찾는다
			String t = str.substring(0, i);
			if (map.containsKey(t)) { // 일치하면 종료
				w = t;
				widx = i - 1;
				break;
			}
		}
		// 해당하는 색인번호를 답에 넣고, 입력에서 w를 제거한다
		answer.add(map.get(w));
		if (str.equals(w)) { // W와 전체문자열이 같으면 종료
			return;
		}
		// 입력에서 처리되지않은 글자가 있다면(c), w+c를 사전에 등록한다
		// 아까 찾은 W의 인덱스에 2를 더해 잘라서 1글자 더 추가된 단어를 만든다  
		String wc = str.substring(0, widx + 2);
		if (!map.containsKey(wc)) {
			maxLen = Math.max(maxLen, wc.length()); // 최대 길이 갱신
			map.put(wc, mapIdx++); // 사전에 등록
			getLZW(str.substring(w.length())); // W를 제외한 문자열을 넘긴다
		}
	}

}