Programmers : 문자열 압축

문제링크

풀이요약

구현

풀이상세

1. split 함수를 통해 문자열을 갯수만큼 쪼갠다.

2. split 함수에서 반환된 벡터값을 비교하며, 이전 값과 현재값이 동일한지 본다. 만약 이전 값과 동일한 경우 cnt 를 올리고, 그렇지 않은 경우는 cnt 값을 반영하여 문자열을 압축한다. (현재 cnt 가 0이면 생략하고, 그렇지 않은 경우에만 cnt 값을 반영한다)

3. 현재 쪼갠 문자열이 압축되어 나타나는 것과 지금껏 압축해온 문자열 가운데 최소길이를 업데이트 한다. (맨 앞 문자열 기준으로 동일하게 쪼개져야 하기 때문에, 전체 길이의 절반까지만 쪼개어도 답을 찾을 수 있다)

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<string> split(string s, int cnt) {
    vector<string> temp;
    int idx=-1;
    string ts="";
    while(++idx<s.size()) {
        ts += s[idx];
        if(ts.size()==cnt) {
            temp.push_back(ts);
            ts = "";
        } 
    }
    temp.push_back(ts);
    return temp;
}

int solution(string s) {
    int answer = s.size();
    vector<string> v_sp;
    for(int i=1; i<=v_sp.size()/2; i++) {
        v_sp = split(s,i);
        string prev = v_sp[0];
        int curr_cnt = 0;
        string curr_str = "";
        for(int i=1; i<v_sp.size(); i++) {
            if(curr_str.size()>answer) break;
            if(prev == v_sp[i]) {
                curr_cnt++;
            } else {
                curr_str += (!curr_cnt ? "" : to_string(curr_cnt+1))+prev;
                curr_cnt = 0;
            }
            prev = v_sp[i];
        }
        curr_str += (!curr_cnt ? "" : to_string(curr_cnt+1))+prev;
        answer = min(answer, (int)curr_str.size());   
    }
    return answer;
}