해결방법

• 압축 최대 길이는 문자열의 길이 그대로이므로, answer를 문자열의 길이로 초기화한다.
• 문자열을 묶는 단위의 최대 길이는? 문자열 길이의 절반 이다.
  문제에서 요구하는 것은 문자열을 잘라 압축하여 표현한 문자열 중 "가장 짧은 것"의 길이 이므로, 문자열을 묶는 단위는 최대 문자열 길이의 절반까지만 살펴보면 된다.
• 기준문자열을 기준으로, 다음 문자열과 같다면? 반복횟수를 세어주면 된다.
• 만약 다르다면 압축 결과에 추가해주면 되는데
  • 반복횟수가 1이라면, 숫자는 추가하지 않는다.
  • 반복횟수가 1 이상이라면 숫자를 먼저 추가해준다.
    이 때 숫자를 문자로 바꿔서 압축 결과에 추가! (to_string 이용)
  • 기준문자열을 압축결과에 추가해준 다음, 기준문자열을 다음 문자열로 바꿔주고, 반복횟수를 1로 초기화한다.
• 만약 단위만큼 끝까지 살펴봤는데 문자열이 남아있다면? 추가해준다.
  • 위와 동일
• 압축문자열의 길이와 answer 를 비교하여 최솟값으로 갱신해준다.
  

소스코드

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

int solution(string s) {
    int size = s.size();
    unsigned long answer = size;
    for(int unit = 1; unit<=size/2; unit++){
        int cnt = 1;
        string str = s.substr(0,unit);
        string tmp = "";
        for(int i = unit; i<size; i+=unit){
            if(str == s.substr(i,unit)) cnt++;
            else{
                if(cnt>1) tmp += to_string(cnt);
                tmp += str;
                str = s.substr(i,unit);
                cnt = 1;
            }
        }
        if(cnt>1) tmp += to_string(cnt);
        tmp += str;
        
        answer = min(answer, tmp.size());
    }
    
    return answer;
}

제출결과

문자열을 다루는건 어렵다