처음에 문제를 잘못 읽어서 같은 단위로 자르는 줄 모르고 허프만 코딩인가 했다😂 그게 아니고 무조건 같은 단위로 자르는 거니까 하나씩 다 해보면 된다! 어차피 문자열의 최대 길이가 1000이니까 다 해봐도 시간초과는 안 날 것이다.
#include <string>
#include <algorithm> // max
using namespace std;
int solution(string s) {
int size = s.size();
int answer = size;
int i, j, cnt;
string result, now;
for (i = 1; i <= size / 2; i++) { // 자르는 단위
result = "";
now = s.substr(0, i);
cnt = 1;
for (j = i; j < size; j += i) {
if (now == s.substr(j, i)) cnt++;
else {
if (cnt > 1) result += to_string(cnt);
result += now;
now = s.substr(j, i);
cnt = 1;
}
}
if (cnt > 1) result += to_string(cnt);
result += now;
answer = min(answer, (int)result.size());
}
return answer;
}