프로그래머스 | Level 2 | 압축

Programmers | Level 2 | 압축

Problems

• 📘 Src: Programmers
• 🗂️ Cat: Hash Table

Description

신입사원 어피치는 카카오톡으로 전송되는 메시지를 압축하여 전송 효율을 높이는 업무를 맡게 되었습니다. 메시지를 압축하더라도 전달되는 정보가 바뀌어서는 안 되므로, 압축 전의 정보를 완벽하게 복원 가능한 무손실 압축 알고리즘을 구현하기로 했습니다.

어피치는 여러 압축 알고리즘 중에서 성능이 좋고 구현이 간단한 LZW(Lempel-Ziv-Welch) 압축을 구현하기로 했습니다. LZW 압축은 1983년 발표된 알고리즘으로, 이미지 파일 포맷인 GIF 등 다양한 응용에서 사용되었습니다.

LZW 압축은 다음 과정을 거칩니다:

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

압축 알고리즘이 영문 대문자만 처리한다고 할 때, 사전은 다음과 같이 초기화됩니다. 사전의 색인 번호는 정수값으로 주어지며, 1부터 시작합니다.

색인 번호	1	2	3	...	24	25	26
단어	A	B	C	...	X	Y	Z

예를 들어 입력으로 KAKAO가 들어온다고 하자.

• 현재 사전에는 KAKAO의 첫 글자 K는 등록되어 있으나, 두 번째 글자까지인 KA는 없으므로, 첫 글자 K에 해당하는 색인 번호 11을 출력하고, 다음 글자인 A를 포함한 KA를 사전에 27번째로 등록합니다.
• 두 번째 글자 A는 사전에 있으나, 세 번째 글자까지인 AK는 사전에 없으므로, A의 색인 번호 1을 출력하고, AK를 사전에 28번째로 등록합니다.
• 세 번째 글자에서 시작하는 KA가 사전에 있으므로, KA에 해당하는 색인 번호 27을 출력하고, 다음 글자 O를 포함한 KAO를 29번째로 등록합니다.
• 마지막으로 처리되지 않은 글자 O에 해당하는 색인 번호 15를 출력합니다.

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

이 과정을 거쳐 다섯 글자의 문장 KAKAO가 4개의 색인 번호 [11, 1, 27, 15]로 압축됩니다.

입력으로 TOBEORNOTTOBEORTOBEORNOT가 들어오면 다음과 같이 압축이 진행됩니다.

현재 입력(w)	다음 글자(c)	출력	사전 추가(w+c)
T	O	20	27: TO
O	B	15	28: OB
B	E	2	29: BE
E	O	5	30: EO
O	R	15	31: OR
R	N	18	32: RN
N	O	14	33: NO
O	T	15	34: OT
T	T	20	35: TT
TO	B	27	36: TOB
BE	O	29	37: BEO
OR	T	31	38: ORT
TOB	E	36	39: TOBE
EO	R	30	40: EOR
RN	O	32	41: RNO
OT		34

Constraints

• 입력으로 영문 대문자로만 이뤄진 문자열 msg가 주어집니다.
• msg의 길이는 1 글자 이상, 1000 글자 이하입니다.

Examples

msg	answer
KAKAO	[11, 1, 27, 15]
TOBEORNOTTOBEORTOBEORNOT	[20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34]
ABABABABABABABAB	[1, 2, 27, 29, 28, 31, 30]

Solutions

• ⏳ TC: O(n)
• 💾 SC: O(n)

import java.util.*;

class Solution {
    public int[] solution(String msg) {
        // 사전 초기화
        Map<String, Integer> dictionary = new HashMap<>();
        int dictSize = 26;
        for (int i = 0; i < 26; i++) {
            dictionary.put(String.valueOf((char) ('A' + i)), i + 1);
        }

        List<Integer> result = new ArrayList<>();
        String w = "";
        
        for (char c : msg.toCharArray()) {
            String wc = w + c;
            if (dictionary.containsKey(wc)) {
                w = wc;
            } else {
                result.add(dictionary.get(w));
                dictionary.put(wc, ++dictSize);
                w = String.valueOf(c);
            }
        }
        
        if (!w.isEmpty()) {
            result.add(dictionary.get(w));
        }
        
        return result.stream().mapToInt(i -> i).toArray();
    }
}

Approaches

이 문제는 LZW 압축 알고리즘을 구현하는 문제로, 해시 테이블을 사용하여 문자열 패턴을 관리하고 인덱스를 할당합니다. 이를 통해 문자열을 효율적으로 압축하고, 각 패턴에 대한 색인 번호를 출력할 수 있습니다. 다음과 같은 접근 방식을 사용합니다:

• 사전 초기화:
  • 길이가 1인 모든 단어(A부터 Z까지)를 포함하도록 사전을 초기화합니다.
  • 각 단어는 고유의 색인 번호를 가지며, 1부터 시작합니다.
• 입력 문자열 순회:
  • 입력 문자열을 순회하면서 현재 입력과 일치하는 가장 긴 문자열 w를 찾습니다.
  • w에 해당하는 사전의 색인 번호를 출력하고, 사전에 w+c를 추가합니다.
  • 다음 문자를 처리하기 위해 w를 초기화합니다.
• 결과 출력:
  • 마지막으로 남아있는 문자열 w에 해당하는 색인 번호를 결과에 추가합니다.
  • 최종 결과를 배열로 변환하여 반환합니다.

이 알고리즘의 시간 복잡도는 O(n)이며, 공간 복잡도도 O(n)입니다. 이는 주어진 문제를 효율적으로 해결하는 데 충분합니다.