[Programmers] 2019 카카오 개발자 겨울 인턴십 - 문자열 압축

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

 

 

문제 풀이:

주목할 조건:

• 앞에서부터 반복되는 문자열이어야 한다.
• 반복되는 문자열의 길이가 같아야 한다.
• 반복되는 문자열의 길이가 [10,100) 사이의 숫자이면 길이가 2 증가하고 e.g. 11abc. -> 문자열 길이 5 

 

풀이:

1. 문자열의 길이를 1부터 n/2가지 늘려가면서 중복 문자열 개수를 카운트
   • 최대한 길게 겹치는 문자는 절반씩 같은 문자 e.g. abcabc
2. 맨 처음 문자열을 sub라고 두고, 다음부터 보는 문자열을 cnt로 둔다
   • 같으면 cnt++
   • 아니면 지금까지 겹친 문자열 개수 계산한 다음 cnt=0으로 초기화

 

 

 

 

소스 코드:

int solution(string s) {
	int len = s.size();
	int answer = len;

	for (int i = 1; i <= len / 2; i++) {
		string sub= s.substr(0, i);
		int cnt = 0;
		int tmp = 0;
		for (int j = i; j <= len - i; j+=i) {
			string cur = s.substr(j, i);
			if (sub == cur) cnt++;
			else {
				tmp += cnt * i;
				if (cnt == 999) tmp -= 4;
				else if (cnt >= 99)tmp -= 3;
				else if (cnt >= 9)tmp -= 2;
				else if (cnt >= 1) tmp -= 1;
				cnt = 0;
				sub = cur;
			}
		}
		tmp += cnt * i;
		if (cnt == 999) tmp -= 4;
		else if (cnt >= 99)tmp -= 3;
		else if (cnt >= 9)tmp -= 2;
		else if (cnt >= 1) tmp -= 1;
		answer = min(answer, len - tmp);
	} 

	return answer;
}