문자열 조작 1 - 완전 탐색

주어진 문자열을 압축 했을 시 길이가 가장 작아지는 문자열의 길이를 출력

 

문자열 내 반복되는 문자열이 존재 할 시 반복되는 횟수만큼 압축하라는 문제다.

입출력 예제

aabbaccc -> 2a2ba3c

 

제한사항: 문자열의 길이 1 이상 1000이하

#include <string>
#include <vector>
#include <limits.h>

using namespace std;

int solution(string s) {
    int answer = INT_MAX;
    int len = s.length();
    
    if(len == 1)
        return 1;
    
    for(int selection = 1; selection <= len/2; ++selection)
    {
        string compressedString = "";
        string target = s.substr(0, selection);
        
        int compressed = 1;
        for(int j = selection; j < len; j += selection)
        {
            string compared = s.substr(j, selection);
            if(target.compare(compared) == 0)
            {
                compressed++;
            }
            else
            {
                if(compressed > 1)
                {
                    compressedString += to_string(compressed) + target;
                }
                else
                {
                    compressedString += target;
                }
                
                target = compared;
                compressed = 1;
            }
        }
        
        if(compressed > 1)
        {
            compressedString += to_string(compressed) + target;
        }
        else
        {
            compressedString += target;
        }
        
        int lengthOfCompressedString = compressedString.length();
        
        if(answer > lengthOfCompressedString)
            answer = lengthOfCompressedString;
    }
    
    return answer;
}