문자열 압축 (프로그래머스)

특정 알고리즘 유형을 필요로 하는 문제는 아니었다.

 

문제에서 요구하는 답은 압축된 문자열의 길이 이므로 직접 압축된 문자열을 만들어볼 필요는 없었다.

 

우선 압축할 문자열의 길이를 기록한다. 

 

쪼갤 수 있는 횟수만큼 쪼갠다.

만약 쪼갠 문자열이 그 이후에 쪼갤 문자열과 같다면 카운트를 증가시킨다.  

만약 서로 다르다면 지금까지 카운트 값을 검사했던 (기록한 카운트 값 * 측정한 문자열 크기)만큼 기록한 문자열 길이에서 빼주고 압축된 정보 크기만큼 더해준다. 

aaaaabbbbacccc(a 5번 중복) -> bbbbacccc(검사했던 알파뱃 삭제) -> 5abbbbacccc(압축된 정보 추가) ->...

 

이 작업을 쪼갤 수 있는 횟수 1부터 전체 문자열의 절반 크기까지 반복한다.

전체 문자열의 절반까지만 구하는 이유는 그 이상부터는 쪼갰을 때 문자열의 크기가 항상 서로 달라 중복될 수 없어서 의미가 없기 때문이다. 

aaabbbaaabbb -> aaabbb, aaabbb -> 중복 체크 가능

(문자열 절반 크기 + 1 만큼 쪼개는 경우)
aaabbbaaabbb -> aaabbba, aabbb -> 중복 체크 불가능

 

코드는 다음과 같다.

#include <string>
using namespace std;

int solution(string s) 
{
    int answer = s.length();
    
    // 1부터 문자열 길이 절반 크기까지 쪼갠다.
    for(int i = 1; i <= s.length() / 2; ++i)
    {
        // 미리 압축할 문자열 길이를 기록한다.
        int len = s.length();
        for(int j = 0; j < s.length(); ++j)
        {
            for(int count = 0, z = i; j + z < s.length(); z += i)
            {
                // 현재 쪼갠 문자열과 다음에 쪼갤 문자열이
                // 서로 같은 경우 카운트 값 증가
                if(s.substr(j, i) == s.substr(j + z, i)) ++count;
                // 만약 서로 다른 경우
                else
                {
                    // 중복되는 문자열 크기를 빼준다.
                    len -= i * count;
                    // 압축 정보 크기만큼 더한다.
                    if(count) len += to_string(count + 1).length();
                    // 다음 쪼갤 위치로 이동한다.
                    j += z - 1;
                    break;
                }
                
                // 한번이라도 압축된 상태에서 뒤 계산이 안된 경우
                if(j + z + i >= s.length())
                {
                    len -= i * count;
                    len += to_string(count + 1).length();
                    j += z;
                }
            } 
        }     
        if(len < answer) answer = len;     
    }
    return answer;
}