Level 2. 문자열 압축

Level 2. 문자열 압축

 

 

압축할 수 있는 모든 경우의 수를 찾아 실제 압축을 진행해 해결했다.

• 문자열의 길이가 4라면, 3개 단위부터는 압축이 불가능하므로 확인하지 않아도 된다.

 

벡터에 n 길이로 잘린 문자열들을 담은 후, 앞에서부터 동일한 문자열의 개수를 찾아 압축 문자열에 추가한다.

• 마지막 문자열 처리를 위해 쓰레기 값인 "0"을 추가해줬다.

 

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

using namespace std;

string compress(string& s, int n)
{
    vector<string> v;

    for (int pos = 0; pos < s.length(); pos += n)
        v.emplace_back(s.substr(pos, n));

    v.emplace_back("0");

    string result, current = v.front();
    int cnt = 0;

    for (string& str : v)
    {
        if (str == current)
        {
            ++cnt;
        }
        else
        {
            result += (cnt <= 1) ? "" : to_string(cnt);
            result += current;

            current = str;
            cnt = 1;
        }
    }

    return result;
}

int solution(string s)
{
    size_t answer = s.length();
    int last = answer * 0.5f;

    for (int i = 1; i <= last; ++i)
        answer = min(compress(s, i).length(), answer);

    return answer;
}