[2023년 11월 22일]문자열 압축

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

구현 아이디어 5분 구현 ...

풀이

2번째 푸는데 틀렸다. 게다가 1번째엔 풀었다... 다음에는 꼭 맞춘다.

#include <string>
#include <vector>

using namespace std;

int solution(string s) {
    int answer = 0;
    
    int min_len = s.length();
    if(min_len == 1) return 1;
    
    for(int i = 1; i <= s.length() / 2 + 1; ++i)
    {
        // 기본 1개.
        int cnt = 1;
        
        // 문자열 일단 자르기.
        string sub_s;
        for(int j = 0; j < i; ++j) sub_s += s[j];
        
        string comp_s, result;
        for(int j = i; j < s.length(); j += i)
        {
            comp_s.clear();
            for(int k = j; k < j + i && k < s.length(); ++k) comp_s += s[k];
            
            if(sub_s == comp_s)
                ++cnt;
            else
            {
                if(cnt != 1) result += to_string(cnt) + sub_s;
                else result += sub_s;
                sub_s = comp_s;
                cnt = 1;
            }
        }
        if(!comp_s.empty())
        {
            if(cnt != 1) result += to_string(cnt) + comp_s;
            else result += comp_s;
            comp_s.clear();
        }
        
        if(min_len > result.length())
            min_len = result.length();
    }
    
    return answer = min_len;
}

---

다른 사람의 풀이

이해하기 편한 풀이라 공부했다. 문자열을 미리 다 나눈 뒤에 비교하는 방법이다.

#include <string>
#include <vector>

using namespace std;

vector<string> divide(const string& s, int n)
{
    vector<string> tmp;
    for(int i = 0; i < s.length(); i += n)
        tmp.push_back(s.substr(i, n));
    
    return tmp;
}

int solution(string s) {
    int answer = 0;
    int min_len = s.length();
    string cur_s;
    
    vector<string> div;
    for(int i = 1; i <= s.length() / 2 + 1; ++i)
    {
        div = divide(s, i);
        cur_s = div[0];
        string result;
        int cnt = 1;
        
        for(int j = 1; j < div.size(); ++j)
        {
            if(div[j] == cur_s) ++cnt;
            else
            {
                if(cnt != 1) result += to_string(cnt);
                result += cur_s;
                cur_s = div[j];
                cnt = 1;
            }
        }
        if(cnt != 1) result += to_string(cnt);
        result += cur_s;
        
        min_len = min_len < result.length() ? min_len : result.length();   
    }
    
    return answer = min_len;
}