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

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

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

주어진 조건을 보고 그에 맞는 문자열 처리를 해주면 되는 문제입니다.

substr을 사용하여 문제를 해결할 수 있습니다.

 

문제 접근법

• 주어진 문자열을 압축하기 위해서 문자열을 자르고 자른 문자열을 주어진 문자열과 비교합니다.
• 이 때, 자른 문자열의 최대 길이는 주어진 문자열의 길이의 절반입니다.
• 절반을 초과하는 길이부터는 압축이 불가능하기 때문입니다.
• 즉, 문자열을 1부터 문자열의 길이 / 2 까지의 길이로 나눠가면서 압축을 진행해보면 되는 문제입니다.

 

아래는 코드입니다.

#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;
}