2020 KAKAO BLIND RECRUITMENT문자열 압축

너무 오랜만에 하려고 하니까 귀찮아서 대충 짠거같다.

풀기 급급해서 깔끔하게 짜는건 실패한거 같다.

 

요지는 1글자부터 length/2 글자까지 반복해가면서 줄여보고 가장 짧은 글자 수를 반환하면 된다.

늘 풀면서 느끼는건 뭔가 대단한 알고리즘이 있을거 같지만 대부분은 그냥 노가다 코드 짜는 것 뿐인것같다.

#include <string>
#include <vector>

using namespace std;

int check(string& str, int size) {
	string temp;

	string temp1;
	string temp2;

	int count = 1;
	// 생각해보니 매번 자르지말고 size별로 미리 텍스트를 잘라서 vector에 담아놓고 써도 될 것 같다.
	for (int i = 0; i < str.length() - size; i += size)
	{
		temp1 = str.substr(i,  size);
		temp2 = str.substr(i + size, size);

		if (0 == temp1.compare(temp2))
		{
			++count;
		}
		else
		{
			if (count > 1)
				temp += to_string(count);

			temp += temp1;

			count = 1;
		}
	}

	if (count > 1)
		temp += to_string(count);

	temp += temp2;

	return temp.length();
}

int solution(string s) {
    int best = s.length();
    
    for (int i=1; i<=s.length()/2; ++i)
    {
        int res = check(s, i);
        if (best > res)
            best = res;
    }

    return best;
}