[프로그래머스 2레벨] 문자열 압축 (C++)

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(string s) {
    int answer = s.size();
    
    for(int i=1; i<=s.size()/2; i++)
    {
        string tmp = s.substr(0, i);
        string result = "";
        int cnt = 0;
        for(int j=0; j<s.size(); j+=i)
        {
            if(tmp == s.substr(j, i)) cnt++; //같으면 카운팅
            else
            {
                if(cnt>=2) result += to_string(cnt) + tmp; //다르면 누적된 문자열(숫자 + 문자) 저장
                else result += tmp; //문자만 저장
                tmp = s.substr(j, i); //새로운 문자열 시작
                cnt = 1;
            }
        }
        
        // 남은 마지막 문자열 처리
        if (cnt >= 2) result += to_string(cnt) + tmp;
        else result += tmp;
        
        answer = min(answer, (int)result.size());
    }
    return answer;
}

 

최대로 압축할 수 있는 것은 전체 길이의 절반까지 이므로, 반복문을 1부터 전체 길이의 절반까지 돌려주면 된다.

해당 반복문을 사이즈로 이용하여 부분 문자열 tmp와 카운팅할 변수를 선언해준다.

 

이제 전체 문자열 s에서 현재 위치에서 i만큼의 부분 문자열을 체크해 사전에 만든 부분 문자열 tmp과 같은 지 여부를 체크하고 같았을 때 카운팅을 해준다.

다른 경우에는 (카운팅한 숫자 + 문자) 형태의 문자열을 정답 문자열에 저장해주고, 카운팅이 1이라면 문자만 저장한다.

이후에는 새로운 문자열이 시작된 것이므로 현재 j값 기준으로 tmp를 갱신해주고, 카운트 또한 1로 초기화 해준다.

 

반복문 종료 이후에는 남은 마지막 문자열을 똑같이 처리해준다.

answer에는 이렇게 만든 result 문자열의 가장 작은 값을 담아주면 된다.