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

java나 python은 substr이 (start,end)로 end index 전까지인데

 

c++ 의 substr은  (시작위치, 개수) 인걸 헷갈렸었따...

 

문자열은 제일 앞부터 정해진 길이만큼 잘라야 하고

문자열의 길이가 최대 1000이므로 n^2으로 충분히 가능하다.

 

substr으로 정해진길이의 다음 substr을 검사하면서 진행해준다.

 

이때 신경써야할 부분은 cnt의 숫자에 따라 문자열의 길이가 달라진다는 점이다.

최대 1000이므로 적당히 if else로 처리해준다.

 

 

#include <string>
#include <vector>
#include <iostream>
using namespace std;
 
int cnttolen(int cnt) {
    int ret;
    if (cnt == 0) return 0;
    if (cnt < 10) ret = 1;
    else if (cnt < 100) ret = 2;
    else if (cnt < 1000) ret = 3;
    else if (cnt < 10000) ret = 4;
    return ret;
}
 
int solution(string s) {
    int answer;
    int len = s.size();
    answer = len;
    for (int k = 1; k <= s.size() / 2; k++) {
        string cur = s.substr(0, k);
        int tot = len;
        int r = k;
        int cnt = 1;
        while(r+k-1<len){
            string next = s.substr(r, k);
            if (cur == next) {
                cnt++;
            }
            else {
                cur = next;
                if (cnt > 1) {
                    tot -= k * (cnt - 1);
                    tot += cnttolen(cnt);
                }
                cnt=1;
            }
            r += k;
        }
 
        if (cnt > 1) {
            tot -= k * (cnt - 1);
            tot += cnttolen(cnt);
        }
 
        if (tot < answer) answer = tot;
    }
 
 
    return answer;
    
}