설명
1개 이상의 단위로 문자열을 잘라서 압축할 때 압축된 문자열 길이가 가장 작은 것을 찾는 문제이다. 그렇다면 반복문을 돌려서 단위 1부터 문자열을 끝까지 순회하면서 압축된 문자열의 길이가 작을 경우 ans값과 비교하여 갱신시켜 주면 된다.
for (int i = 1; i <= s.length() / 2; i++)
{
int pos = 0;
int len = s.length();
while (1)
{
string unit = s.substr(pos, i); // pos번째부터 i길이 만큼 문자열 자르기
pos += i;
if (pos >= s.length()) break;
}
ans = min(ans, len);
}위 코드는 0부터 i길이 만큼 문자열을 잘라서 unit에 넣고, 다음 문자열 비교를 위해 i길이 만큼 pos를 증가시키고 pos가 문자열 전체 길이와 같을 때까지 반복을 돌린다. 이렇게 하면 맨 처음 길이1 만큼 문자열을 순회하고, 그 다음 길이 2 만큼 잘라서 문자열을 순회하며, 결과적으로 입력이 aabbaccc, len=8이 주어졌을 때 i=4를 마지막으로 순회를 마칠 것이다.
i=2인 경우
unit = aa // (0, 2)
unit = bb // (2, 2)
unit = ac // (4, 2)
unit = cc // (6, 2)
i=4인 경우
unit = aabb // (0, 4)
unit = accc // (4, 4)
int cnt = 0;
while (1)
{
if (unit.compare(s.substr(pos, i)) == 0)
{
cnt++;
pos += i;
}
else
break;
}aabb를 자르고 나서 해야할 일은 그 뒤의 같은 길이로 자른 문자열과 비교를 해서 i길이 만큼 반복되는 횟수를 검사하는 일이다.
while문 안에서 단순히 i길이 만큼 증가시키면서 같지 않은 문자열이 나올 때까지 체크해 나가면서 cnt를 1씩 증가시켜준다.
if (cnt > 0)
{
len -= i * cnt;
if (cnt < 9) len += 1;
else if (cnt < 99) len += 2;
else if (cnt < 999) len += 3;
else len += 4;
}cnt가 1 이상인 경우는 같은 문자열이 하나 이상 반복되었기 때문에 앞에 추가될 숫자도 자릿수만큼 길이에 추가되어야 한다. 만약 abcdabcd(len=8, i=4인 경우)가 나왔으면 cnt=1이기 때문에 if문에 들어갈 것이고, 문자열은 하나만 길이에 추가하면 되기 때문에 len -= 4가 되어 len를 4로 맞춰준다. 그리고 cnt가 1일때 실제 반복된 문자열의 개수는 2였기 때문에, cnt=9이면 숫자는 두자리가 될 것이다. 따라서 s의 길이가 1000 이하이기 때문에 그것까지 고려해서 코드를 구성하면 된다.
코드
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
string s;
cin >> s;
int ans = s.length();
for (int i = 1; i <= s.length() / 2; i++)
{
int pos = 0;
int len = s.length();
while (1)
{
string unit = s.substr(pos, i);
pos += i;
if (pos >= s.length()) break;
int cnt = 0;
while (1)
{
if (unit.compare(s.substr(pos, i)) == 0)
{
cnt++;
pos += i;
}
else
break;
}
if (cnt > 0)
{
len -= i * cnt;
if (cnt < 9) len += 1;
else if (cnt < 99) len += 2;
else if (cnt < 999) len += 3;
else len += 4;
}
}
ans = min(ans, len);
}
cout << ans;
return 0;
}참고
