[programmers][2020카카오공채] 문자열 압축

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

---

aabbccc

가 있을 때, 탐색하는 압축 길이는 길이의 반 이하인 1, 2, 3만 살펴보면 된다.

길이의 반(7/2 =3)보다 큰 수인 4는 반드시 중복되는 수가 하나도 없을 것이기 때문이다. (aabb가 중복될 가능성은 0. 왜냐하면 남은 문자의 길이가 4보다 작기 때문이다.)

 

압축하는 길이를 compression 이라고 했을 때,

#1 문자열 s를 앞에서부터 compression 개수만큼 잘라가며 이전 문자열과 비교한다. 동시에 압축 문자열의 길이(len)를 갱신해나간다.

#2 만약 이전 문자열과 같다면 반복되는 문자열 개수(cnt)를 +1 해준다.

이 때, cnt의 초기 값은 0이 아닌 1이다. (이전 문자열과 다른 경우 현재 탐색 중인 문자열을 개수에 포함해줘야 하기 때문.) 

ex) s = aabbcc, compression = 2라 할때,  bb탐색 시 aa 압축 문자열 길이는 len에 더해주고 cnt는 "bb"를 하나 포함해야 하므로 1로 초기화된다. 

#3 탐색 중인 문자열이 이전 문자열과 다르다면 cnt의 자리 수 + compression을 압축 문자열 길이(len)에 더해준다.

ex) aa가 10개 반복되었다면 압축 문자열은 10aa, aa가 4번 반복되었다면 4aa 이므로 압축 문자열의 길이가 cnt에 따라 달라진다. aa 길이 = compression, 반복 횟수(10, 4) 길이 = cnt 자리 수

#4 문자열 탐색이 끝났을 때, 마지막에 남는 문자열은 그대로 붙여줘야 하므로 문자열 길이 % compression을 len에 더한다.

ex) s = aabbccc, compression = 2인 경우 c가 2로 잘라지지 않으므로 마지막에 c 길이(= 7%2 = 1)만큼 len에 더해준다.

#5 압축 길이에 따른 len을 모두 구한다음 이 중 최소 값이 정답이 된다.

 

int solution(string s) {
    length = s 문자열 길이
    answer = length // 정답이 될 수 있는 최대값은 s 문자열 길이
    
    // #1
	for(compression = 1..length/2){ 
    	cnt = 1 // 반복되는 문자열 개수
        len = 0 // compression 단위로 잘라서 압축할 때 생성되는 압축 문자열 길이
        before = s[0..compression]
        for(i = compression부터 s를 compression 길이만큼 쪼갤 수 있을 때 까지. 
        	compression만큼 증가시킨다.){
            now = s[i..i+compression]
            if(이전문자열과 같은 경우(now = before)) { // #2
            	cnt += 1
            } else { // #3
        		len = len계산()
                cnt += 1
            }
            before = now
        }
        len = len계산() // 계산 안된거 마저 계산
        
        // #4
        len += length % compression
        
        // #5
        answer = len, answer 중 최소값
    }
    return answer
}

int len계산() {
	if(cnt > 0) len += cnt 자리 수
    len += compression 
    return len
}

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/programmers/Algorithm/programmers/2020카카오공채/문자열 압축.cpp