[프로그래머스] (문자열) 카카오 문자열 압축 c++

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

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

 

문자열 압축을 다루는 문제

문자열을 다루는 것은 굉장히 귀찮고 힘들다
분명 편한 방법이 있을 것 같다.
계속해보면서 찾는 수밖에 없을 것 같다.



반복문 조건에
여태까지 압축한 최소 문자열 길이가
지금 압축해야 할 문자열 길이보다 짧으면 break 해주니
평균 시간이 더 줄었다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int mysqrt(int cnt)
{
    int x=cnt;
    for(int i=1; i<4; i++)
    {
        x=x/10;
        if(x==0)
        {
            return i;
        }
    }
}

bool check(string str,string temp)
{
    if(temp.length()<str.length())
    {
        return false;
    }
    
    bool sw=true;
    for(int i=0; i<str.length(); i++)
    {
        if(str[i]!=temp[i])
        {
            sw=false;
            break;
        }
    }
    
    return sw;
}

//https://programmers.co.kr/learn/courses/30/lessons/60057
int solution(string s) {
    int answer = 10000;
    string str;
    string temp;
    int myanswer;
    
    if(s.length()==1) return 1;
    
    for(int i=1; i<s.length()-1; i++)
    {
       
        str=s.substr(0,i);
        myanswer=i;
        int cnt=1;
        for(int j=1; j<s.length()/i; j++)
        {
        	
            if(i>=answer) break;  //break문
            
            temp=s.substr(j*i,i);
            if(check(str,temp))
            {
           
                cnt++;
            }
            else
            {
          
                myanswer=myanswer+i;
                if(cnt>1) myanswer+=mysqrt(cnt);
                str=temp;
                cnt=1;

            }
        }
        
     
        myanswer=myanswer+s.length()%i;
        if(cnt>1)myanswer+=mysqrt(cnt);
        if(answer>myanswer) answer=myanswer;
          
    }
    
    return answer;
}

카카오 문자열 압축 실행시간