2020 KAKAO BLIND RECRUITMENT - 1. 문자열 압축

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

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

카카오 1번 문제

주어지는 문자열을 앞에서부터 단위 문자열 개수로 자르면서 겹치는 문자열을 합쳐주는 문제이다.

나는 문자열 자체를 수정하지 않고 단순히 길이만 증감시켜주는 방법으로 문제를 해결했다.

문자열을 무조건 앞에서부터 순서대로 자르는 문제가 아니라 중간에서 자르는게 가능한 문제였다면 꽤 복잡한 문제였을 것 같다.

#include <iostream>
#include <string>
#include <math.h>

using namespace std;

int solution(string s) {
	int idx, cnt, answer;
	string s1 = "", s2 ="";
	int flag = 1;

	answer = s.length();
	s1 += s[0];
	//1글자부터 s.length()/2 글자까지 검사
	for (int i = 1; i <= s.length() / 2; i++) {
		//글자 길이를 현재 문자열의 길이로 초기화
		cnt = s.length();
		idx = 0;
		flag = 1;
		if (i == 1) idx = 1;
		//
		while (idx <= s.length() - i) {
			for (int j = idx; j < idx + i; j++) s2 += s[j];
			if (!s1.compare(s2)) { // s1 == s2
				flag++;
				cnt -= i;
			}
			else { // s1 != s2
				//cnt에 flag의 자릿수만큼 더해준다.
				if (flag != 1) cnt += (log10(flag) + 1);
				flag = 1;
				s1 = s2;
			}
			idx += i;
			s2 = "";
		}
		//s1 == s2가 true인 상태로 while문 빠져나왔을 경우 flag 따로 체크해준다.
		if (flag != 1) cnt += (log10(flag) + 1);
		if (answer > cnt) answer = cnt;
	}
	return answer;
}

int main() {
	string s;
	cin >> s;
	cout << solution(s);

	return 0;
}