240215 압축

public int[] solution(String msg) {
	List<Integer> compressedMsg = new ArrayList<>();
	int nextCode = 1;
	Map<String, Integer> dictionary = new HashMap<>();

	for (int i = 65; i <= 90; i++) {
		String character = String.valueOf((char) i);
		dictionary.put(character, nextCode++);
	}

	int i = 0;
	while (i < msg.length()) {
		int maxLength = msg.length() - i;
		int j = maxLength;
		while (j > 0 && !dictionary.containsKey(msg.substring(i, i + j))) {
			j--;
		}
		String substring = msg.substring(i, i + j);

		if (i + j == msg.length()) {
			compressedMsg.add(dictionary.get(substring));
		} else {
			substring = msg.substring(i, i + j + 1);
			compressedMsg.add(dictionary.get(substring.substring(0, substring.length() - 1)));
		}
		dictionary.put(substring, nextCode++);
		i += Math.max(1, j);
	}

	int[] result = new int[compressedMsg.size()];
	for (int k = 0; k < result.length; k++) {
		result[k] = compressedMsg.get(k);
	}

	return result;
}

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