https://school.programmers.co.kr/learn/courses/30/lessons/60057

침착하게 규칙을 찾으면 해결되는 문제.

문제 설명

문제에서 추출할 수 있는 정보는 다음과 같다.

• 같은 값이 연속해서 나타나는 부분을 (숫자)(값)으로 처리해야 한다.
• 1개 이상의 단위로 문자열을 잘라서 압축을 진행할 경우 만들 수 있는 가장 짧은 문자열의 길이를 구해야 한다.

해결 과정

1. 압축할 문자열의 길이를 1부터 문자열의 절반 길이까지 점점 늘려가며 이웃한 문자열끼리 동일한지 판정한다.
2. 동일한 경우 해당 길이만큼 빼주고, 동일하지 않으면 해당 문자열이 존재했던 수만큼 앞에 숫자를 붙여줘야 하는데, 직접 문자열에 숫자를 붙이지 말고 숫자의 문자열 상의 길이(10이면 2, 100이면 3)만큼 더해준다.
3. 최솟값을 갱신한다.

이때 동일한 경우가 2번 감지되는 "aaa"의 경우 앞에 붙는 숫자가 "3"임에 주의한다. 이 케이스를 생각해주지 않으면 만약 aaaaaaaaaa의 경우 9번 감지되지만 10a이기 때문에 오답이 발생하게 된다.

소스 코드

#include <string>
#include <iostream>
#include <vector>

using namespace std;

int solution(string s) {
    int answer = s.size();
    int maxcutsize = s.size()/2;
    
    for(int a=1; a<=maxcutsize; a++){
        int nowlen = s.size();
        int cnt = 0;
        for(int i=0; i<s.size()-a; i+=a){
            string target = s.substr(i, a);
            string next = s.substr(i+a, a);
            if(target == next){
                cnt++;
                nowlen -= a;
            } else {
                if(cnt > 0) nowlen += to_string(cnt+1).size();
                cnt = 0;
            }
        }
        if(cnt > 0) nowlen += to_string(cnt+1).size();
        cnt = 0;
        answer = min(answer, nowlen);
    }
    return answer;
}