[C++] 프로그래머스 : 문자열 압축

https://programmers.co.kr/learn/courses/30/lessons/60057

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

 

1. 첫 코드

- 패턴찾는경우 len/2까지만 탐색

- 마지막 자투리 문자열 더하는 코드를 줄일 수 없을까

#include <string>
#include <vector>

using namespace std;

int solution(string s) {
	int answer = 0;

	int sLen = s.length();
	answer = sLen;
	
    for(int i=1; i<=sLen/2; i++){ // i개 단위
        string res = "";
        
        string bss = s.substr(0,i);
        int cnt = 1;
        int idx = i; // next tok start index
        
        while(idx + i <= sLen){
            string tmp = s.substr(idx, i);
            
            if(bss == tmp){
                cnt++;
            }
            else{
                if(cnt > 1)
                    res += to_string(cnt);
                res += bss;
                
                cnt = 1;
                bss = tmp;
            }
            idx += i;
        }
        if(cnt > 1)
            res += to_string(cnt);
        res += bss;
        
        if(idx < sLen){
            res += s.substr(idx, sLen-idx);
        }
        
        if(answer > res.length())
            answer = res.length();
    }
    

	return answer;
}