[프로그래머스] Level2 - 문자열 압축

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/60057

코딩테스트 연습 - 문자열 압축

[풀이과정]

1. 문자열 길이가 n인 경우 1~n/2으로 잘랐을 경우를 모두 구한다. (n/2를 넘게 자르는 것은 불가능)

 

2. 길이 len으로 자른 경우 길이가 len인 substring을 한개씩 비교하면서 앞의 것과 같으면 압축 가능한 개수를 저장하는 cnt를 1 더해준다.

 

3. 다른 문자열이 나오면 cnt의 길이 + len만큼을 ret에 더해준다.

 (cnt를 string으로 변환 후 size 구함, cnt가 1인 경우 더해주지 않음)

 

4. 다음 index (i+len)이 s의 길이를 초과하는 경우 더 이상 압축이 불가능 하므로 남아있는 것을 더해준다.

   (s2.size()만큼 더해주는 이유는 제일 마지막 부분 문자열은 len보다 작을수도 있기 때문에)

 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int sol(string& s, int len) {

	int ret = 0;

	int cnt = 1;
	for (int i = len; i < s.size() ; i += len) {
		string s1 = s.substr(i-len, len);
		string s2 = s.substr(i, len);
		//cout << s1 << "," << s2 << endl;
		if (s1 == s2) {
			cnt++;
		}
		else {
			ret += len;
			if (cnt != 1) ret += to_string(cnt).size();
			cnt = 1;
		}
		if (i + len >= s.size()) {
			ret += s2.size();
			if (cnt != 1) ret += to_string(cnt).size();
		}
		//cout << ret << endl;

	}
	return ret;
}

int solution(string s) {
	if (s.size() == 1) return 1;

	int answer = 10000;

	for (int i = 1; i <= s.size() / 2; i++) {
		answer = min(answer,sol(s, i));
	}

	return answer;
}

https://github.com/has2/Algorithm/blob/master/programmers/level2/%EB%AC%B8%EC%9E%90%EC%97%B4%20%EC%95%95%EC%B6%95.cpp