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

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

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

문제 접근법

• 1자리 부터 시작하여 문자열 길이의 절반까지의 길이 만큼의 문자의 중복을 체크한다.
  • 문자열 길이 절반을 초과하면 중복이 나오지 않기 때문이다.
  • 중복되는 문자의 갯수를 체크 후 중복 되지않는 문자를 만나면 중복되는 문자의 갯수와 해당 문자를 더한 문자열을 만든다.
  • 중복 되지 않았던 문자를 기준으로 다시 중복을 체크한다.
  • 만약 문자열의 길이 % 중복체크용 문자 길이가 0이 아니라면 중복체크를 하다가 남는 문자가 존재하는 것이므로, 해당 길이를 체크하여 문자를 더해줘야 한다

#include <string>
#include <vector>
 
using namespace std;
 
int solution(string s) {
    int answer = 1000;
    int len = s.size();
    int tLen = len / 2;
    
    if(len == 1) return 1;
    
    for(int i = 1; i <= tLen; i++)
    {
        string s1 = "";
        string str = s.substr(0, i);
        
        int count = 1;
        
        for(int j = i; j <= len; j += i)
        {
            if(str == s.substr(j, i))
            {
                count++;
            }
            else
            {
                if(count == 1)
                {
                    s1 += str;
                }
                else
                {
                    s1 += to_string(count) + str;
                }
                
                str = s.substr(j, i);
                count = 1;
            }
        }
        
        if(len % i != 0)
        {
            s1 += s.substr(len - len % i, len % i);
        }
        
        if(answer > s1.size())
        {
            answer = s1.size();
        }
    }
    
    return answer;
}