[Programmers] 문자열 압축 - travelbeeee

문제 : 카카오 2020 BLINE RECRUITMENT '문자열압축'

---

구현

 예시 5번을 잘 이해하면 쉽게 구현할 수 있는 문제입니다. 문자열의 모든 지점에서 압축크기만큼 압축을 진행할 수 있는게 아니라, 시작지점부터 압축크기만큼 잘라야 합니다.

 1 ~ (문자열의길이 / 2) 까지 각각 다 압축을 진행해보고 가장 작은 길이 값을 return 해주면 됩니다.

 p1 : 문자열의 현재 시작 지점을 가리키고 있는 포인터

 p1 에서부터 i (현재압축크기) 만큼 같은 쌍이 몇개 나오는지 count를 합니다. 이때, count 값이 1이면 자기 자신이랑만 같다는 뜻으로 압축을 할 필요가 없습니다. 따라서, p1 을 p1 + i 로 보내준 후 다시 같은 과정을 반복하면 되고, count 값이 1보다 크다면 압축을 진행할 수 있으므로 압축을 진행하고 p1 을 p1 + count * i 로 보내주면 됩니다. 

#include <string>
#include <vector>
#include<algorithm>

using namespace std;

int get_length(int n) {
	int ret = 0;
    while(n){
    	ret++;
        n /= 10;
    }
    return ret;
}

int solution(string s) {
	int answer = s.length();
	int start = 1, end = s.length() / 2;
	for (int i = start; i <= end; i++) {
		int  p1 = 0, tempAns = s.length();
		while (p1 <= s.length() - 2 * i) {
			// p1 에서부터 i개 씩 같은지 다른지 체크해보자.
			int cnt = 0, jump = 0;
			while (1) {
				bool check1 = false;
				for (int j = 0; j < i; j++) {
					if (s[p1 + j] != s[p1 + jump + j]){
						check1 = true;
						break;
					}
				}
				if (!check1) // p1에서부터 i개씩 다 같음 -> p1 + i 로 jump를 이동.
					jump += i;
				else
					break;
				cnt++;
			}
			if (cnt == 1){ // p1에서부터 i개씩 다 같은게 자기 자신 밖에 없음.
				p1 += i; // 그러면 p1 시작 위치를 그냥 이동( 압축된게없음 )
			}
			else{ // p1에서부터 i개씩 다 같은게 있음!
				p1 += cnt * i; // 일단 p1을 저 앞으로 이동
				tempAns -= i * cnt; // 답 갱신
				tempAns += get_length(cnt) + i;
			}
		}
		answer = min(answer, tempAns);
	}
	return answer;
}

---