프로그래머스 - 문자열 압축(2020 KAKAO BLIND RECRUITMENT)

시험 기간이라 짬나는 대로 한 문제씩 풀어보기로 하였다.

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(string s) {
    int answer = 0;
    int cnt = 0;
    answer = s.size();
    for(int size = 1; size <= s.size() / 2; size++)
    {
        string tmp = "";
        for(int i=0; i<s.size(); i+=size)
        {
            if (i + size + size <= s.size() && s.substr(i, size) == s.substr(i + size, size))
                cnt++;
            else
            {
                if (cnt != 0)
                    tmp += to_string(cnt + 1);
                tmp += s.substr(i, size);
                cnt = 0;
            }
        }
        answer = min(answer, (int)tmp.size());  
    }
    return answer;
}

처음에는 우선 문자열 길이가 1인 문자열로 잘랐을 때 어떻게 표현되는지에 대해서 반복문으로 작성해보았다. 

작성하고 나니, 길이를 1이 아닌 size로 두어 최대 길이인 size / 2까지 반복문을 돌리면 되겠다는 생각이 들어서 위와 같이 작성하였다.

다만, 주의해야 할 점은 substr을 할 시 i + size부터 size까지의 부분 문자열을 가져오게 되는데, 만약 문자열의 인덱싱을 넘는 경우를 따로 처리해줘야 했다. 

그래서 if문 가장 앞에 인덱스를 넘는지 안넘는지 체크하고, 문자열 덩어리를 비교해 주었더니, 통과를 받게 되었다.