문자열 압축
문제 해석
주어진 문자열을 특정 단위로 잘라서 압축하는 방법 중 가장 짧게 나타낼 수 있는 길이를 측정하는 문제입니다.
예를 들어 “aabbaccc”를 2개 단위로 압축하면 “2a2ba3c”로 압축이 가능합니다.
설계(20)
가장 naive하게 생각해보면 1~문자열 최대길이까지의 단위로 압축을 해보면 되기 때문에 O(N)xO(N) = O(N^2)에 원하는 값을 얻을 수 있습니다.
하지만, 총 길이의 절반 이상의 단위는 압축이 불가능한것이 자명하므로 절반의 단위까지만 탐색합니다.
주의할 점은 압축 가능여부를 판단할 때 문자열 범위를 넘어설 수 있기 때문에 모듈로를 이용하여 아예 범위를 못넘게 제한을 둡니다.
모든 범위를 탐색한 후, 마지막 남은 target문자열 또는 모듈로로 제한한 나머지 문자열을 마저 추가해주면 완전한 압축이 됩니다.
구현(35)
코드
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int solution(string s) {
int len = s.length();
int answer = len;
for (int i = 1; i <= int(len / 2); i++) {
string target = "";
string ans_s = "";
int start = 0;
int count = 1;
while (start < len - len % i) {
if (target.length() < i) {
target += s[start];
}
else {
bool possible = true;
for (int j = 0; j < i; j++) {
if (target[j] != s[j + start]) {
possible = false;
break;
}
}
// 같은 문자열이면 카운트 증가
if (possible) {
count++;
start += i - 1;
}
else {
if (count > 1) ans_s += to_string(count);
ans_s += target;
target = "";
count = 1;
start--;
}
}
start++;
}
if (count > 1) ans_s += to_string(count);
ans_s += target;
if (len % i != 0) ans_s += s.substr(len - len % i);
if (answer > ans_s.length()) answer = ans_s.length();
}
return answer;
}
디버깅
문자열처리 부분이 설계할 때에 한번에 눈에 들어오지 않아서 코딩을 하면서 생각한 탓에 몇번의 디버깅을 하게 되었습니다.
마지막 남은 문자열을 추가해주는 부분을 제대로 구현하지 않았습니다.
possible==false인 경우(압축이 불가능한 문자열) 인덱스를 증가시키지 않도록 처리해주었어야하는데 그부분을 생각하지 못했습니다.
제출결과
마무리
별도의 알고리즘이 필요하지 않은 문제이지만 문자열을 처리해야하는 까다로운 문제였습니다.