문자열 압축(2020 카카오 블라인드 채용)

문제 링크

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

 

풀이

bundle변수를 선언하여 1개씩 묶은 것부터 문자열의 length/2까지 묶은 것의 개수를 vector 컨테이너에 넣고 최소를 return 하였다.

 

 

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

using namespace std;

int solution(string s) {
    int answer = s.length();
    int bundle = 1;
    int len = s.length();
    vector<int> v;
    
    // cout<< "s = "<< s<< endl;
    
    while(bundle <= len/2)
    {
        string repeat = s.substr(0, bundle);
        string total = "";
        int count = 1;
        int i;
        for(i=bundle; i<len; i+=bundle)
        {
            string sub = s.substr(i, bundle);
            if(repeat == sub)
            {
                count++;
            }
            else
            {
                if(count>1) total += to_string(count) + repeat;
                else total += repeat;
                count = 1;
                repeat = sub;
            }
        }
        // cout<<"count = "<< count << endl;
        // 후처리
        if(count>1) total += to_string(count) + repeat;
        else
        {
            for(i-=bundle; i<len; i++)
                total += s[i];
        }
        // cout<< "bundle = " <<bundle <<"-----";
        // cout<< "total = " << total<< endl;
        bundle++;
        v.push_back(total.length());
    }
    
    for(int i=0; i<v.size(); i++)
    {
        if(answer > v[i]) answer = v[i];
    }
    
    return answer;
}