[Programmers] 2020 KAKAO BLIND RECRUITMENT : 문자열 압축 (C++)

https://school.programmers.co.kr/learn/courses/30/lessons/60057

프로그래머스

걸린 시간 : 46분 43초

---

차근차근 해나가면 어렵지 않은 문자열 문제다. 단, 해줘야 할 예외처리가 꽤 많은 편이다.

알고리즘

1. for 문으로 1부터 문자열 길이의 절반까지 모두 단위로 생각해 문자열을 압축해본다. 문자열 길이의 절반이 넘을 경우 압축이 될 수가 없으므로 압축해볼 필요가 없다.
   여기서, 문자열의 길이가 1일 경우 예외처리를 해야 한다. 마지막에 테스트해보다가 알게 되었다. 테스트케이스 5번이 실패가 떴는데, 극단적인 경우 (문자열 길이 1)를 테스트해보니까 바로 걸렸다.
2. 문자열 압축을 하는데, 문자열을 단위씩 끊어 frag를 만든다.
   1. 만약 이것이 직전 문자열과 같다면 같았던 개수를 뜻하는 samenum만 증가한다.
   2. 만약 이것이 직전 문자열과 다르다면 직전 문자열이 얼마나 반복되었는지, 그 자릿수를 리턴값에 더해주어야 한다.
      예를 들어, 문자열이 24회 반복되었다면 2를, 5회 반복되었다면 1을 더해주어야 한다. 문자열의 길이니까! 단, 1회 반복된 경우 1을 쓰지 않는다고 했다.
      이제 직전 문자열을 뜻하는 old 를 최신화 해주고, samenum도 리셋한다.
      또한 새로운 문자열의 개수도 더해주어야 하니 리턴값에 단위만큼 더해준다.
   3. 모두 끝났을 때 남은 문자열이 있으면 그대로 뒤에 붙여준다고 했다.

정답 코드

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int dig(int n) {
    int ret = 0;
    while (n > 0) {
        ret++;
        n /= 10;
    }
    return ret;
}
 
int compress(string s, int unit) {
    string old = s.substr(0, unit);
    int ret = unit;
    int idx = unit;
    int samenum = 1;
    while (idx <= s.size() - unit) {
        string frag = s.substr(idx, unit);
        if (old == frag) {
            samenum++;
        }
        else {
            if (samenum > 1)
                ret += dig(samenum);
            old = frag;
            samenum = 1;
            ret += unit;
        }
        idx += unit;
    }
    if (samenum > 1)
        ret += dig(samenum);
    if (idx < s.size()) ret += s.size() - idx;
    return ret;
}
 
int solution(string s) {
    int answer = 2100000000;
    if (s.size() == 1) return 1;
    for (int i = 1; i <= s.size() / 2; i++) {
        answer = min(answer, compress(s, i));
    }
    return answer;
}