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

문제

---

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

풀이

---

문자열을 나눠 공통된 문자열을 찾는 문제로, 문자열을 추출하고 남은 문자열과 비교하여 최소 길이를 탐색한다. 다만, 나누는 문자열의 길이가 1/2 보다 크면 압축하는 의미가 없어, 탐색에 제한을 두고, 비교 문자열이 연속 반복되지 않는 경우, 자르는 단위만큼 cnt를 더해 문자열의 크기를 계산한다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(string s)
{
    int answer = s.size();
    int length = s.size();


    for (int i = 1; i <= length / 2; i++)
    {
        int cnt = 1;

        string result = "";
        string overlap = s.substr(0, i);

        for (int j = i; j <= length; j += i)
        {
            if (overlap == s.substr(j, i))
            {
                cnt++;
            }

            else
            {
                if (cnt == 1)
                {
                    result += overlap;
                }

                else
                {
                    result += to_string(cnt) + overlap;
                }

                overlap = s.substr(j, i);
                cnt = 1;
            }

        }

        if ((length % i) != 0)
        {
            result += s.substr((length / i) * i);
        }

        if (answer > result.size())
        {
            answer = result.size();
        }

    }

    return answer;
}