프로그래머스 | 압축 (Java)

🔒 문제

프로그래머스 Lv.2 2018 KAKAO BLIND RECRUITMENT [3차] 압축

🔑 해결

LZW(Lempel-Ziv-Welch) 압축을 구현하여 제시된 문자열을 압축한 후의 사전 색인 번호를 배열로 return하는 solution함수를 작성하는 문제이다.

문제에서 제공하는 LZW 압축과정을 순서대로 따라가며 풀면 되는 문제였다.
1. 길이가 1인 모든 단어를 포함하도록 사전을 초기화한다.
-> HashMap dictionary를 생성하여 색인(Integer형)을 key 값으로, 길이가 1인 모든 단어(=알파벳)을 value로 저장한다.
2. 사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다.
-> 입력된 문자열 msg를 끝에서부터 한 글자씩 잘라 dictionary에 존재하는 value값인지 확인(dictionary.containsValue(w))한다.
3. w에 해당하는 사전의 색인 번호를 출력하고, 입력에서 w를 제거한다.
-> w가 dictionary에 존재한다면 for문을 통해 w를 value로 갖는 key를 찾아서 list에 저장한다. msg를 i에서부터 끝까지 잘라 입력에서 w를 제거한다.
4. 입력에서 처리되지 않은 다음 글자가 남아있다면(c), w+c에 해당하는 단어를 사전에 등록한다.
-> msg의 길이가 0이상이라면 처리되지 않은 글자가 남아있다는 뜻으로, w와 남은 msg의 첫 번째 글자(c = msg.charAt(0))를 합해 사전에 등록한다.
5. 단계 2로 돌아간다.
-> msg가 ""이 될 때까지 while문을 반복한다.

🔓 코드

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
class Solution {
    public int[] solution(String msg) {
        int[] answer;
        ArrayList<Integer> list = new ArrayList<>();
        
        // 길이가 1인 모든 단어를 포함하도록 사전을 초기화
        Map<Integer, String> dictionary = new HashMap<>();
        for (int i = 1; i < 27; i++) {
			char alphabet = (char)(i+64);
			dictionary.put(i, String.valueOf(alphabet));
		}
        
        while(!msg.equals("")) {
        	// 사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다
        	for (int i = msg.length(); i > 0; i--) {
				String w = msg.substring(0, i); // 끝에서부터 자르기
				if (dictionary.containsValue(w)) { // w가 dictionary에 존자한다면
					for (int j = 1; j <= dictionary.size(); j++) { // w를 value로 갖는 key를 찾아
						if (dictionary.get(j).equals(w)) {
							list.add(j); // 색인 번호를 list에 저장
							break;
						}
					}
					msg = msg.substring(i, msg.length()); // 입력에서 w를 제거
					if (msg.length() > 0) { // 입력에서 처리되지 않은 다음 글자가 남아있다면, 사전에 등록
						dictionary.put(dictionary.size()+1, w+msg.charAt(0));
					}
					break;
				}
			}
        }
        
        answer = new int[list.size()];
        int i = 0;
        for (Integer integer : list) {
			answer[i] = integer;
			i++;
		}
        
        return answer;
    }
}