[Programmers] 문자열 압축

문자열을 개수별로 잘라서 같은 문자열이 존재하면 압축한다. 이 과정을 거친 후 문자열의 최소 길이를 출력하는 문제이다.

문제 해결 전략
문자열의 길이가 1000이하라는 점을 고려해 보았을 때 완전탐색을 하더라도 반복횟수가 그리 많지 않을 것이라 생각했다.

문자열을 크기가 1부터 최대 문자열의 길이/2 까지 나눌 수 있다. 문자열의 길이의 절반보다 큰 부분으로 나누게 되면 뒷부분과 일치하는 부분이 없기 때문이다.

그래서 크기를 1부터 문자열의 길이/2 까지로 하여 반복문을 돌린다.

반복문 안에서는 해당 문자열을 맨 앞에서 부터 크기만큼 잘라서 비교를 해야 한다.

문자열을 크기만큼 자른 뒤 이전에 자른 문자열과 비교하여 일치하면 개수를 늘려주고 다르다면 이전 문자열에 대하여 일치하는 개수와 문자열을 저장해 준다.

그리고 이러한 반복은 현재 탐색 구간에서 부터 크기만큼 자를 수 없을 때 까지(정한 크기보다 개수가 적게 남을 때 까지) 반복하여 이런 경우가 생기면 그냥 뒤에 이어 붙인다.

이렇게 매 경우 문자열을 만들어 크기를 비교하여 최소값을 반환해 준다.

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(string s) {
    int answer = 0;
    
    answer = s.size();
    
    for(int k=1;k<s.size()/2+1;k++){
        int idx = 0;
        int l;
        string str = "";
        int cnt = 1;
        string ss = "";
        while(1){
            string tmp = "";
            if(idx + k > s.size()){
                l = s.size() - idx;
                if(cnt != 1)
                    ss += to_string(cnt);
                ss += str;
                for(int i=idx;i<s.size();i++)
                    ss += s[i];
                break;
            }
            for(int i=0;i<k;i++){
                tmp += s[i+idx];
            }
            if(str == "")
                str = tmp;
            else if(str == tmp){
                cnt++;
            }else{
                if(cnt != 1){
                    string kk = to_string(cnt);
                    cnt = 1;
                    ss += kk;
                }
                ss += str;
                str = tmp;
            }
            idx += k;
        }
        answer = min((int)ss.size(),answer);
    }
    
    return answer;
}

출처 : 프로그래머스
https://programmers.co.kr/learn/courses/30/lessons/60057