2020 카카오 공채 : 문자열 압축

[문제 링크]

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

---

문자열의 길이가 최대 1000이므로 모든 경우에 대해 시도해보는 O(N^2) 알고리즘을 구현해도 무난히 통과할 수 있다.

 

입력받은 문자열을 압축하기 전 길이가 최댓값이기 때문에 answer를 압축하기 전 길이로 초기화해주었다.

 

그다음 2중 for문을 통해 문자열을 1 ~ (s.length() / 2) 개 단위로 잘랐을 때 만들어지는 압축 문자열 중 길이가 가장 짧은 값을 answer에 갱신해주면 정답을 얻을 수 있다.

---

#include <string>
#include <vector>

using namespace std;

int solution(string s) {
	int sLen = s.length();
	int answer = sLen;
	
	for (int i = 1; i <= sLen / 2; i++)
	{
		string temp;
		string idx = s.substr(0, i);
		int cnt = 1;
		int here;

		for(here = i; here + i <= sLen; here += i)
		{
			if (idx == s.substr(here, i))
				cnt++;
			else
			{
				if (cnt > 1)
					temp += to_string(cnt) + idx;
				else
					temp += idx;

				idx = s.substr(here, i);
				cnt = 1;
			}
		}

		if (cnt > 1)
			temp += to_string(cnt) + idx;
		else
			temp += idx;

		temp += s.substr(here);

		answer = answer < temp.length() ? answer : temp.length();
	}

	return answer;
}

알고리즘 200일 프로젝트 - 138 day