[2018_Blind_Kakao] 압축

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

코딩테스트 연습 - [3차] 압축

 

문제에 LZW 압축 알고리즘에 대한 설명이 나와있다.

 

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

 

풀고나서 든 생각이지만 처음 2번 조건에만 집중하면 시간을 단축해 풀 수 있을 것 같았다..

 

내가 접근한 방식은

 

1. 일단 알파벳 "ABCDEFGHIJKLMNOPQRSTUVWXYZ"인 문자열과 이 문자열의 한 단위마다 저장되는 map을 만들었다.

(문제에서 대문자만 처리한다고 했으니 대문자에 대한 문자열만 만들었다.)

 

2. 입력으로 들어오는 msg를 1번에서 만든 문자열에서 찾는다.

 

3. 없을 경우 msg의 길이를 하나 줄여서 부분 문자열을 만들고 다시 찾는다.

 

4. 부분 문자열로 만든 msg가 1번에서 만든 문자열에 발견되었으면 그 index 값이 출력되는 값이고 이 부분 문자열을 1번에서 만든 문자열 뒤에 붙여주고 1번에서 만든 문자열 길이 + 1을 해준다.

 

1 ~ 4번 방식이 문제에서 준 조건을 그대로 코드로 옮긴 것이다.

 

이 접근 방식대로 풀면 문제가 풀린다.

 

#include <string>
#include <vector>
#include <map>

using namespace std;

vector<int> solution(string msg) {
    vector<int> answer;
    
    string alpa = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

    map<string, int> dict;

	for (int i = 0; i < 26; i++) {
		string s;
		s += alpa[i];
		dict[s] = i + 1;
	}

	string w = msg;
	int index = 27;

	while (1) {
		if (msg.length() == 0) break;

		if (dict[w] == 0) {
			w = w.substr(0, w.length() - 1);
		}
		else {
			msg = msg.substr(w.length());

			if (dict[w] != 0) {
				answer.push_back(dict[w]);
			}

			//남아 있는 문자가 있을 경우 다음 문자를 w에 더해서 사전에 추가
			if (msg.length() > 0) {
				string temp = w;
				temp += msg[0];
				dict[temp] = index;
				index += 1;

				w = msg;
			}
		}
	}
    
    return answer;
}