[프로그래머스 2020 KAKAO BLIND RECRUITMENT] 문자열 압축

문제

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

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

 

문제 풀이

 1. 반복되는 문자열의 길이 l은 1<=l <= s.length()이며, s를 l단위로 압축 할 때 만들 수 있는 가장 짧은 길이를 구하면 된다.

 

 2. s를 l만큼씩 탐색한다고 할 때, 같은 문자열이 연속해서 반복되면 몇 번 연속으로 반복되는지 체크하고 s의 끝까지 탐색이 끝나면 문자열이 반복된 횟수 d도 그 길이를 계산하여 len에 더해준다.

• 압축의 시작점을 st라 할 때 압축되는 끝점은 $st + 2*l-1$이고, 이는 항상 s의 마지막 인덱스보다 작아야한다.
  
  

• 따라서 그 끝점이 s의 마지막 인덱스보다 크거나 같을 땐 (압축할 수 없을 때) 문자의 개수만큼 더해준다. 

 

 

코드

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int solution(string s) {
	int sz = s.length(), ans = sz;
	for (int l = 1; l <= sz / 2; l++) {
		int len = 0, d = 1;
		for (int st = 0; st < sz; st += l) {
			d = 1;
			if (st + 2 * l - 1 < sz) 
				while (st + 2 * l - 1 < sz && s.substr(st, l) == s.substr(st + l, l)) d++, st += l;
			else {
				len += sz - st;
				break;
			}
			if (d == 1) len += l;
			else {
				int n = 0;
				for (int i = d; i; i /= 10) n++;
				len += n + l;
			}
		}
		ans = min(ans, len);
	}
	return ans;
}