(코딩테스트)문자열 압축

"ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다. 

이러한 조건에 맞춰 문자열을 압축하는 문제이다. 

처음에는 무조건 균등한 크기로 잘라야 하는 줄 알고 규격에 맞춰 문자열을 잘랐는데, 그렇게 푸는건 아니었고,

어떠한 범위로 보았을때 가장 짧은 문자열을 만들 수 있느냐는 문제였다.

int solution(string s) {
	int answer = s.length();
    //함수를 처음 호출 했을 때 알 수 있는 문자열의 최소길이는
    원래 문자열의 길이이다.//
    
	string out;
	string call;
	string dst;
    //
    call= 범위에 맞게 문자를 받는다.
    dst=call이 지난번에 가졌던 문자를 받는다.
    out=함축된 문자열의 결과를 낸다.
    //
    
	for (int i = 1; i <= s.length()/2; i++) {
    //i는 범위를 지정한다. 처음엔1개씩 비교하고,
    그 다음은 2개씩 비교하는 식이다.
    그렇기에 i는 문자열 절반의 길이를 넘지 못한다.//
    
		out = "";
		call = "";
		dst = "";
		int lapf = 1;
        //i가 루프를 돌때마다 모든것을 초기화 해준다.//
        
		for (int j = 0; j <= s.length(); j+=i) {
        //j는 i의 범위만큼 커지고, 그것을 기준으로 잘라 call에 넣어준다.//
        
			call = s.substr(j, i);
            //그것을 수행하는 함수//
            
			if (dst ==call) {
				lapf++;
			}
            //dst와 call을 비교하고, 몇번 문자가 반복되었는지 체크한다.
            문자는 기본 하나이기 때문에 lapf=1로 초기화되어 있다.//
            
			else if (lapf > 1) {
				out += to_string(lapf) + call;
				lapf = 1;
			}
            //lapf>1은 같은 문자가 반복되었음을 의미한다.
            그땐 out에 반복된 횟수와 해당 문자를 추가하고
            lapf를 초기화한다.else if에 유의.//
            
			else {
				out += call; 
				lapf = 1;        
			}
            //조건에 전부 맞지 않으면 반복되지 않는
            별개의 문자로 판단한다. 반복횟수가 없는 문자는
            횟수를 적지 않기에 문자만 추가한다.//
            
			dst = call;
            //dst는 call을 받는다.//
		}
        
		if (out.length()>0&&out.length()<answer) {
			answer = out.length();
		}
        //이 코드에서 out이 가질 수 있는 가장 작은 길이는 0이다.
        왜냐면 ""로 초기화가 되있으니까! 그래서 &&연산자를 이용한다.
        answer보다 out의 길이가 작으면 answer를 out의 길이로 바꾸고 
        루프를 돈다.//
        
	}
	return answer;
    //전부 비교해 보았을때 가장 작은 문자열의 길이를 리턴한다.//
}

보다보면 가장 짧게 나올 수 있는 문자열의 길이만 구하는 건데 문자열을 아예 만들어 버리는 코드라는 것을 알 수 있다.

이유는 두가지인데 첫번째는 그냥 그렇게 구현하는게 더 쉬워보였고, 두번째는 명색에 문자열 압축인데 길이만 내는게 좀 

아쉬워서 였다. 물론, 반복횟수가 앞에 있고 문자가 뒤에 있어야 하는데, 그 반대로 나오기는 하지만...

그 부분은 문자열 길이에 변화를 주는 것이 아니니 타협을 조금 봤다.