[Level_2 / C++ / 카카오] 문자열 압축

 

이 문제의 핵심은 문자열의 절반만 확인하면 된다는 것이다. 

첫번째 예제에서 크기가 8인 문자열이 주어졌다면 

1부터 4사이즈만큼만 반복문을 돌리면된다.

 

즉, 사이즈가 1~4인 문자열을 돌아보면서 같으면 cnt값을 증가하고 다르면 이전에 증가시켰던 cnt값을 스트링으로 바꾸고 비교해왔던 문자열을 뒤에 붙인다. 그리고 비교해왔던 문자열을 현재 자른 문자열로 교체한다.  

 

* 파라미터 값으로 받아온 문자열이 사이즈가 1이였다면 바로 return 1을 해준다. 

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

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

 

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