[프로그래머스/20년 카카오 블라인드] 문자열 압축(Lv.2), C++

문자열 압축(링크)

문자열의 길이가 N 일 때 1 개 단위, 2 개 단위, 3 개 단위... N / 2 개 단위로 잘라본다. (당연히 절반 이상으로 자르면 더 이상 반복되지 않으므로 압축되지 않는다.)

 

나머지는 단순히 문자들을 순회하며 이전의 단위 문자열과 같은 지 센다. 개수를 덧붙인 새로운 문자열을 만드는 것 보다 경우에 따라 길이값을 늘려가며 정수 길이값 정답을 찾는게 더 효율적이다. 

 

예를 들어 1 개 단위로 자르고 문자열이 aaabbb 라면 a 3 개를 확인한 시점에 개수를 센 정수 변수의 자릿수( = 1) + 단위( = 1) 를 정답에 더하는 식이다. 자릿수를 더하는 이유는 만약 a 가 17 개라면 2 자리만큼 압축된 문자열이 늘어나는 것이므로 자릿수를 더해야 한다.

 

// 정수 n 을 받으면 자릿수를 계산해 반환.
int cntNum(int n) {
	int ret = 0;
	while (n) { n /= 10; ++ret; }
	return ret;
}

int solution(string s) {
    int answer = s.size();
	int slen = s.size();

	int unit = 1; // 1 개 단위부터 잘라 나간다.
	string str;

	while (unit <= slen / 2) { // 전체 길이의 절반까지 단위를 증가.

		str = s.substr(0, unit);
		int i = 0, cnt = 0, len = 0;;

		while (i + unit <= slen) {

			if (str == s.substr(i, unit)) ++cnt;
			else {
            	// 1 개인 경우 숫자가 안 붙고, 2 개 이상의 경우 자릿수를 더한다.
				len += (cnt == 1) ? unit : unit + cntNum(cnt);
				str = s.substr(i, unit);
				cnt = 0;
				continue;
			}

			i += unit;
		}

		len += (cnt == 1) ? unit : unit + cntNum(cnt);
		// 문자열을 모두 확인하지 못 한 경우 나머지 개수만큼 더한다.
		if (i < slen) len += slen - i;
		if (len < answer) answer = len;

		++unit;
	}
   
    return answer;
}