문제

이야 수업 시간에 배웠던 LZW 압축을 직접 구현해 볼 줄이야

이론 시간에는 꽤나 헷갈렸는데 구현하고 보니까 간단해서 놀람,,

#include <string>
#include <vector>
#include <map>
using namespace std;

map<string, int> dict;

void initDict() {
	int i;
	for (i = 0; i < 26; i++) {
		string tmp(1, 'A' + i);
		dict[tmp] = i + 1; // init dict
	}
}

vector<int> solution(string msg) {
	vector<int> answer;
	int i, j;

	initDict();

	for (i = 0; i < msg.size(); i++) {
		string tmp = "";

		j = i; // 사전에서 찾아볼 단어의 길이
		tmp += msg[j];

		while (dict.find(tmp) != dict.end()) {
			j++;
			tmp += msg[j];
		}

		dict[tmp] = dict.size() + 1;
		tmp.pop_back();
		answer.push_back(dict[tmp]);
		i = j - 1;
	}

	return answer;
}