[kakao blind 2020] 문자열 압축 - 문자열, 구현

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

코딩테스트 연습 - 문자열 압축

주어진 문자열을 압축한다고 했을 때 압축되는 단위는 1부터 문자열의 길이 / 2 가 될 수 있다.

이를 이용해서 1. 압축되는 단위를 정하고, 2. 이 단위 만큼 압축 가능한 substring의 갯수를 세고, 3. 압축이 되었을 때의 문자열 길이 중 최소길이를 구하면 된다. 

3번이 좀 햇깔릴 수 있는데 압축된 문자열 길이를 모두 제외한 다음, 압축된 길이의 자릿수만큼 더해주면 된다. 

9a, 99a, 999a, 1000a 와 같이 총 4가지 경우가 나올 수 있다

#include <string>
#include <vector>

using namespace std;

int solution(string s) {
    int ans = s.length();

    for (int i = 1; i <= s.length() / 2; ++i) {
        int pos = 0;
        int len = s.length();  // 압축됬을때 길이

        while (1) {
            string cut = s.substr(pos, i);  // 압축단위 1~s.length()/2 까지 체크
            pos += i;
            if (pos >= s.length()) break;

            int cnt = 0;
            while (1) {
                if (cut.compare(s.substr(pos, i))) break;  // 다음 컷끼리 다르면 종료

                ++cnt;
                pos += i;
            }

            if (cnt) {
                len -= i * cnt;  // 압축된만큼 빼주고 압축된 길이의 자릿수만큼 더해주기
                if (cnt < 9)
                    len += 1;
                else if (cnt < 99)
                    len += 2;
                else if (cnt < 999)
                    len += 3;
                else
                    len += 4;
            }
        }

        if (ans > len) {
            ans = len;
        }
    }

    return ans;
}