프로그래머스 - 문자열 압축

프로그래머스 - 문자열 압축

문자열을 자르는 단위는 1부터 시작해서 최대 문자열의 길이 / 2 까지이다.

먼저, 문자열을 substr을 사용해 자른 뒤 문자열 벡터를 저장해둔다.
해당 벡터를 순회하면서 만약 i번째 문자열이 i+1번째와 같으면 i+2번째와 비교하면서 i+k번째까지 비교한다.
이렇게하면 몇 개의 문자열이 압축될지 알아낼 수 있다.

"aabbaccc"로 예를 들어보면,
문자열을 1, 2, 3, 4 단위로 나눈다.
1단위로 나누면 a, a, b, b, a, c, c, c로 나뉘어지기 때문에 2a2ba3c로 된다.
2단위로 나누면 aa, bb, ac, cc로 나뉘어지기 때문에 aabbaccc로 된다.
3단위로 나누면 aab, bac, cc로 나뉘어지기 때문에 aabbaccc로 된다.
4단위로 나누면 aabb, accc로 나뉘어지기 때문에 aabbaccc로 된다.

따라서 답은 7이 된다.

코드는 아래와 같다.

#include <string>
#include <vector>
#include <cstdio>
#include <map>
#include <climits>

using namespace std;

string s;
int solve(int len)
{
    vector<string> r;
    for(int i=0;i<s.size();i+=len) 
        r.push_back(s.substr(i, len));
    
    int size = r.size();
    string result = "";
    for(int i=0;i<size;i++) {
        int idx = 1;
        while(1) {
            if(i + idx > size - 1)
                break;
            if(r[i].compare(r[i+idx]) != 0) 
                break;
            idx++;
        }
        if(idx != 1) 
            result += to_string(idx);
        result += r[i];
        i += idx - 1;
    }
    
    return result.size();
}
int solution(string input) {
    if(input.size() == 1)
        return 1;
    
    s = input;
    int answer = INT_MAX;
    int len = s.size() / 2;
    for(int i=0;i<len;i++) 
        answer = min(solve(i + 1), answer);
    
    return answer;
}