[알고리즘C++]문자열 압축

오늘의 문제

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

문자열 압축

나의 풀이

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(string s) {
    int size = s.size();
    int answer = size;
    string comp;
    for(int i=1;i<size;i++){
        int subAnswer =size;
        comp = s.substr(0, i);
        int count =1;
        for(int j=i;j<=size-i;j+=i){
            if(s.substr(j, i) == comp){
                subAnswer -=i;
                count++;
                if(j+i> size-i)
                    subAnswer += to_string(count).size();
            }else{
                if(count>1) {
                    subAnswer += to_string(count).size();}
                count=1;
                comp = s.substr(j, i);  
            }
        }
        answer = min(answer, subAnswer);
    }
    return answer;
}

모범 답안

#include <bits/stdc++.h>
using namespace std;

int f(int n) {
    if (n == 1) return 0;

    int ret = 0;
    while (n) ret++, n /= 10;
    return ret;
}
int solution(string s) {
    int answer = s.size(), n = s.size();
    unordered_set<string> S;

    for (int i = 1; i * 2 <= n; ++i) {
        S.clear();
        int j, len = 0, cnt = 1;
        string prv = s.substr(0, i);
        S.insert(prv);

        for (j = i; j < n; j += i) {
            if (S.find(s.substr(j, i)) != S.end()) ++cnt;
            else {
                len += f(cnt) + i;
                S.erase(prv);
                S.insert(prv = s.substr(j, i));
                cnt = 1;
            }
        }

        len += cnt > 1 ? f(cnt) + i : n - j + i;
        answer = min(answer, len);
    }
    return answer;
}

배울 점

• 문제를 잘 안읽고 풀기 시작한게 문제였음. 1개씩 잘라서 하는건데, 하나 건너뛰고 그런거 생각하다보니 코드가 산으로 갔음.... 앞으로 문제를 꼼꼼히 따져봐야할 것 같다.
• 모범답안 사람은 set집합에 잘라넣은 후 비교를 한다. 잘라 넣는 동안에 차라리 비교를 하는게 낫지 않을까 싶다.