[프로그래머스] 문자열 압축

풀이)

완전탐색문제이다.

문자열을 앞에서부터 길이 1 ~ 문자열의 절반길이 +1 까지 자른 뒤,  

(묶는 단위가 절반이 넘으면 당연히 같을 수 없으므로)

자른 문자열이 뒤에 있는지 확인해준 문제이다.

예시의 aabbacc로 설명하자면

aabbaccc

먼저 길이 1로 자른다.

a -> a랑 같은 문자열이 있는 지 확인, 바로 뒤에 있음 -> 또 있는지 확인, 없어서 stop

b -> b랑 같은 문자열이 있는 지 확인, 바로 뒤에 있음 -> 또 있는지 확인, 없어서 stop

a -> a랑 같은 문자열이 있는 지 확인, 없음 stop

c -> c와 같은 문자열이 있는 지 확인, 바로 뒤에 있음 -> 또 있는지 확인, 있음 -> 문자열 길이 끝나서 stop

즉 2a2ba3c

그 다음 길이 2로 자른다

aa -> aa랑 같은 문자열이 있는 지 확인, 없어서 stop

bb -> bb랑 같은 문자열이 있는 지 확인, 없어서 stop

ac -> ac랑 같은 문자열이 있는 지 확인, 없어서 stop

cc -> cc와 같은 문자열이 있는 지 확인,  문자열 길이 끝나서 stop

그 다음 길이 3으로 자른다

aab -> aab랑 같은 문자열이 있는 지 확인, 없어서 stop

bac -> bac랑 같은 문자열이 있는 지 확인, 문자열 길이 끝나서 stop

이런 식으로 구현했다.

코드)

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

int solution(string s) {
    int answer = 1000;
    
    for(int len=1;len<=(s.length()/2 + 1);len++){//자를 길이 절반까지만 봄. +1한 이유는 혹시 s의 길이가 1일수도 있어서
        string cutted="";
        for(int i=0;i<s.length();i++){
            if(i+len-1 < s.length()){
                //cout <<"i: " <<i << " - ";
                string temp = s.substr(i,len);
                //cout << temp << " ";
                int cnt = 1;
                int j = i+len;
                for(j;j<s.length();){
                    if(s.substr(j,len) == temp) {
                        cnt++;
                        j += len;
                    }
                    else break;
                }
                //cout << cnt << " - j: " <<j<<endl;
                i = j-1;
                if(cnt > 1) cutted += to_string(cnt);
                cutted += temp;
            }
            else{
                cutted += s.substr(i);
                break;
            }

        }
        //cout << cutted << endl;
        answer = answer < cutted.length()? answer : cutted.length();
    }
    return answer;
}