[프로그래머스][JAVA]Lv. 2 - 압축

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

프로그래머스

LZW 압축은 다음 과정을 거친다.

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

해당 조건으로 주어진 문자열을 압축하는 문제였다.

String s = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
for (int i = 1; i <= s.length(); i++) {
    numberIndex++;
    hashMap.put(String.valueOf(s.charAt(i-1)), numberIndex);
}
hashMap.put("", 0);

먼저 A-Z을 1~26번으로 hashMap에 넣어주었다. 앞으로 새로운 사전에 추가할 단어는 hashMap에 넣어줄 것이다.

첫 시작을 위해 공백을 0번으로 hashMap에 넣었다.

for (int i = 0; i < msg.length(); i++) {
    StringBuilder sb = new StringBuilder();
    int index = i;
    while (hashMap.containsKey(sb.toString())) {
        if (index >= msg.length()) break;
        sb.append(msg.charAt(index));
        index++;
    }
    if (!hashMap.containsKey(sb.toString())) {
        numberIndex++;
        al.add(hashMap.get(sb.substring(0, sb.length()-1)));
        hashMap.put(sb.toString(), numberIndex);
        i = i + sb.toString().length() - 2;
    } else {
        al.add(hashMap.get(sb.toString()));
        break;
    }
}

0~msg.lenght() 까지 만약 hashMap에 sb가 존재한다면 sb에 다음 글자를 넣어주도록 하고

만약 존재하지 않는다면 정답으로 사용할 ArrayList al에 sb를 추가해주고 hashMap에도 번호와 함께 추가하였다.

그리고 i = i + sb의 길이 - 2로 하여 다음 글자를 탐색해 나가다가 마지막 쯤 사전에 있는 단어 이면서 다음 글자가 없게 되었을 때 al에 추가하고 종료하도록 만들었다.

import java.util.ArrayList;
import java.util.HashMap;
class Solution {
    public int[] solution(String msg) {
        int[] answer;
        int numberIndex = 0;
        HashMap<String, Integer> hashMap = new HashMap<>();
        String s = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        for (int i = 1; i <= s.length(); i++) {
            numberIndex++;
            hashMap.put(String.valueOf(s.charAt(i-1)), numberIndex);
        }
        hashMap.put("", 0);
        ArrayList<Integer> al = new ArrayList<>();
        for (int i = 0; i < msg.length(); i++) {
            StringBuilder sb = new StringBuilder();
            int index = i;
            while (hashMap.containsKey(sb.toString())) {
                if (index >= msg.length()) break;
                sb.append(msg.charAt(index));
                index++;
            }
            if (!hashMap.containsKey(sb.toString())) {
                numberIndex++;
                al.add(hashMap.get(sb.substring(0, sb.length()-1)));
                hashMap.put(sb.toString(), numberIndex);
                i = i + sb.toString().length() - 2;
            } else {
                al.add(hashMap.get(sb.toString()));
                break;
            }
        }
        answer = new int[al.size()];
        for (int i = 0; i < al.size(); i++) {
            answer[i] = al.get(i);
        }
        return answer;
    }
}