문자열을 압축하는 방법에 대한 것 중 가장 압축이 잘된 문자열 길이를 반환하는 것
구현한 기본 컨셉은, 1~ 문자열절반 길이 까지의 (압축할 길이)로 압축해본 모든 문자열을 만들어보고, 그 중 가장 짧은 문자열의 길이를 반환하는 방법으로 했다.
// 처리과정
//1. 문자열 s 입력받는다.
//2. 문자열길이/2 의 결과문자열배열 (resultStrings) 만들어둔다.
//3. 1부터 s length/2 까지 반복한다. (i) - 압축할 길이
// 3.1. 시작(j)부터 (j+압축할길이) 가 length 넘지 않을 때까지 반복한다. (j += 압축할 길이)
// 3.1.1. 압축할 길이만큼씩 substring 한 것을 앞의 substring 과 비교해서
// 3.1.1.1. 같으면 -> count 세둔다.
// 3.1.1.2. 다르면 -> count 확인해서
// 3.1.1.2.1. count == 1 이면, 해당 순서 resultStrings 에다가 현재 substring 저장한다.
// 3.1.1.2.2. count > 1 이면, 해당 순서 resultStrings 에다가 count 와 substring 저장한다.
// 3.2. 압축할 길이로 잘라나가다가 남은 뒷부분을 해당 순서 resultStrings 뒤에 저장해준다.
//4. 다 만들어진 각 압축길이별 resultStrings 에서 제일 짧은 length 구한다.
//5. 가장 짧은 문자열 length 반환한다.
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
using namespace std;
int solution(string s) {
if (s.length() == 1)
return 1;
int substringRange = s.length() / 2;
// 2.
vector<string> resultStrings;
for (int i = 0; i < substringRange; ++i) {
resultStrings.push_back("");
}
// 3.
for (int i = 0; i + 1 <= substringRange; ++i) {
int count = 1;
string nextString;
int j = 0;
while (j + (i + 1) <= s.length()) {
string currentStr = s.substr(j, i + 1);
nextString = s.substr(j + (i + 1), i + 1);
//cout << " " << "currentStr : " << currentStr << " " << "nextString : " << nextString << endl;
if (currentStr == nextString) {
++count;
}
else {
if (count == 1) {
resultStrings[i] += currentStr;
}
else {
stringstream ss;
ss << count;
resultStrings[i] += ss.str();
resultStrings[i] += currentStr;
count = 1;
}
}
j += (i + 1);
}
while (j < s.length()) {
resultStrings[i] += s[j];
++j;
}
}
// 4.
int smallestLength = resultStrings[0].length();
for (int i = 1; i < resultStrings.size(); ++i) {
if (smallestLength > resultStrings[i].length()) {
smallestLength = resultStrings[i].length();
}
}
return smallestLength;
}
//int main() {
// //string test1 = "aabbaccc";
// string test1 = "a";
// string test2 = "ababcdcdababcdcd";
// string test3 = "abcabcdede";
// string test4 = "abcabcabcabcdededededede";
// string test5 = "xababcdcdababcdcd";
//
// cout << "this : " << test1 << endl;
// cout << solution(test1) << endl;
//
//
// return 0;
//}