[Programmers] 문자열 압축(c++)

https://programmers.co.kr/learn/courses/30/lessons/60057

코딩테스트 연습 - 문자열 압축

 

for문 i는 문자열 압축 단위, for문 j는 현재 문자열의 위치를 의미한다.

 

1. comp를 비교대상 문자열으로 초기화한다.

2. j는 i번째부터 시작한다. comp와 비교해서 같으면 cnt++, 다르면 cnt와comp값을 동시에 저장한다. (1일때는 comp값만 저장한다)

3. 다시 comp를 현재 s의 substr(j,i)번째로 초기화 후 2번을 반복한다.

4. 마지막 문자열을 비교할때 comp안의 크기와 문자열 압축단위의 크기 i가 다르다면 result에 그대로 연결한다.

5. 모든 answer중 최솟값이 answer에 저장된다.

 

 

 

**s의 입력의 크기가 1일때 예외처리를 해줘야 함

 

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

int solution(string s) {
    if(s.size() == 1) return 1;
    int answer = 9999999;
    int cnt = 1;
    
    string comp = "";
    for(int i=1;i<s.length()/2+1;i++){
        string result;
        comp = s.substr(0,i);
        for(int j=i;j<=s.length();j+=i){
            
            if(comp == s.substr(j,i)){
                cnt++;
            }
            else{
                if(cnt != 1){
                    result += to_string(cnt);
                }
                result += comp;
                cnt = 1;
            }
        
            comp = s.substr(j,i);
            if(comp.size() != i) result += comp;
            
        }
        
        int len = result.size();
        answer = min(len, answer);
        
    }
    return answer;
}

int main(){
    
    string s = "xababcdcdababcdcd";
    
    solution(s);
    
    return 0;
}