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

프로그래머스

 

입출력 예 #4

 

• 앞에서부터 n개 단위로 문자열을 잘라 압축시킨 뒤의 문자열 길이가 가장 짧은 n의 값을 구하는 문제

 

> 1부터 문자열의 길이까지를 단위로 하여 압축한 뒤 개중 가장 짧은 길이를 리턴

> 입력받은 단위만큼 비교하여 압축이 가능한지 가능하다면 총 몇 번 압축 가능한지 판별

> 이후 압축이 가능하다면 압축된 형태로 str을 갱신 후 나머지 구간을 반복

#include <string>
#include <vector>

using namespace std;

// cnt = 압축 단위, str = 문자열
int stringCompressor(int cnt, string str) {
    for(int i = 0; i < str.size();) {
    	// i부터 cnt만큼 문자열을 자름
        string cmpStr = str.substr(i, cnt);
        
        // cmpStr과 같은 문자열의 개수(자신 포함)
        int cntSameStr = 1;
        
        for(int j = i + cnt;j < str.size(); j += cnt) {
        	// j부터 cnt만큼 자른 문자열이 cmpStr과 같으면 cntSameStr++, 다르면 break
            if(cmpStr == str.substr(j, cnt)) cntSameStr++;
            else break;
        }
        
        // cntSameStr == 1이면 같은 문자열 없음으로 다음 구간으로 넘김
        if(cntSameStr == 1) {
            i += cnt;
            continue;
        }
        
        // cntSameStr의 개수 + cmpStr의 형태로 만듦
        cmpStr = to_string(cntSameStr) + cmpStr;
        // 압축되지 않는 나머지 문자열을 자름
        string remainStr = str.substr(i + cnt * cntSameStr);
        // str의 형태를 갱신
        str = str.substr(0, i) + cmpStr + remainStr;
        
        i += cmpStr.size();
    }
    
    return str.size();
}

int solution(string s) {
    int answer = s.size();
    
    //1부터 해당 문자열의 사이즈만큼 압축을 반복
    for(int i = 1; i <= s.size(); i++) {
        answer = min(answer, stringCompressor(i ,s));
    }
    
    return answer;
}

 

 풀고 나니까 1부터 문자열의 사이즈만큼이 아니라 1부터 문자열 사이즈의 1/2까지만 반복하는 것이 더 효율적이었을 것 같다. 

> 어차피 압축 단위가 문자열의 절반보다 크면 압축 안됨