[알고리즘]프로그래머스 17684번 - [3차]압축

프로그래머스 17684번 - [3차]압축

프로그래머스 17684번 - https://programmers.co.kr/learn/courses/30/lessons/17684

프로그래머스 17684번 - https://programmers.co.kr/learn/courses/30/lessons/17684

프로그래머스 17684번 - https://programmers.co.kr/learn/courses/30/lessons/17684

 

요구사항

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

 

요구사항 분석 및  풀이과정

LZW 압축을 수행하는 작업 이외의 작업은 없으므로 LZW 압축의 수행과정은 본문의 사진을 참고하여주세요.

 

소스코드 작성

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {

	private static Map<String, Integer> defaultDictionary() {
		Map<String, Integer> dictionary = new HashMap<>();
		for (char c = 'A'; c <= 'Z'; c++) {
			dictionary.put(String.valueOf(c), c - 'A' + 1);
		}

		return dictionary;
	}

	public int[] solution(String msg) {
		Map<String, Integer> dictionary = defaultDictionary();

		List<Integer> result = new ArrayList<>();
		for (int start = 0; start < msg.length(); ) {
			int end = start + 1;
			while (end <= msg.length()) {
				String newWord = msg.substring(start, end);
				if (!dictionary.containsKey(newWord)) {
					break;
				}

				end++;
			}

			String existsLongWord = msg.substring(start, end - 1);
			result.add(dictionary.get(existsLongWord));

			String notExistsLongWord = msg.substring(start, Math.min(msg.length(), end));
			dictionary.put(notExistsLongWord, dictionary.size() + 1);

			start += existsLongWord.length();
		}

		return result.stream().mapToInt(Integer::intValue).toArray();
	}
}

 

결과

 

소스코드 깃허브 주소

링크