📒활용개념

1. vector의 부분 삭제 -> .erase(시작점, 갯수)
2. cur, before의 구분으로 문제풀이

📌문제설명

LZW(Lempel-Ziv-Welch)압축을 구현한다. LZW 압축은 1982년 발표된 알고리즘으로, 이미지 파일인GIF 등 다양한 응용에서 사용되었다.
과정
1. 길이가 1인 모든 단어 포함하도록 사전 초기화
2. 사전에 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다.
3. w에 해당하는 사전의 색인번호 출력, 입력에서 w제거
4. 입력에서 처리되지 않은 글자가 남아있다면(c), w+c에 해당하는 단어 사전에 등록
5. 입력이 모두 처리될 때까지 단계2로 돌아가 반복한다.
ex) input -> KAKAO
현재 입력(w) 다음 글자(c) 출력 사전 추가(w+c)
K A 11 27: KA
A K 1 28: AK
KA O 27 29: KAO
O 15

answer = [11,1,27,25]

📌구현

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<string> dic;								//사전

int find (string lzw){							//사전의 색인 번호 출력과 사전에 존재유무 판단.
    for(int i=1; i<dic.size(); i++){
        if(dic[i]==lzw){
            return i;							//사전에 존재
        }
    }
    return 0;									//사전에 존재하지 않음
}

vector<int> solution(string msg) {
    vector<int> answer;
    string a;									//사전 초기화를 위한 string
    string cur;									//현재 입력
    string befor;								//현재를 제외한 가장 최근
    dic.push_back(" ");							//dic[0]을 제외
    
    a="A";
    
    for(int i=1; i<=26; i++){					//dic 초기화
        dic.push_back(a);
        a[0]++;
    }
    
    cur+=msg[0];
    while(msg != ""){
        if(find(cur)>0){						//사전에 존재할 경우
            befor=cur;							
            msg.erase(0,1);						//존재하는 w삭제
            cur+=msg[0];
        }
        else{									//사전에 존재하지 않을 경우
            answer.push_back(find(befor));		//가장 최근 존재 string answer에 push
            befor="";
            dic.push_back(cur);					//존재하지 않는 cur 사전에 등록
            cur=msg[0];
        }
    }
    answer.push_back(find(befor));				//마지막에 존재했던 string answer에 push
    
    return answer;
}

📌주의점

• 문제 이해가 되지 않았던 문제었다.
• 사전에 존재 유무 판단과, 입력값의 끝을 어떻게 판단할 것인가.
• cur과 befor을 활용하여 어떤 값을 사전에 등록하고 어떤 값을 answer에 등록할 것인지를 판단할 수 있어야 한다.