[알고리즘] 프로그래머스_문자열 압축

본 블로그는 비상업적, 비영리적 용도의 학업만을 위해 글을 게시합니다.

1. 문제 분석

• 비교하는 문자의 개수를 고정시켜놨기 때문에, 단순하게 1개, 2개, ..., (문자열의 길이/2)개 순으로 단어들을 잘라서 비교하면 될 것 같다.

2. 문제 풀이 과정(삽질)

• 처음에는 문자열을 최선의 압축을 해야하나 했지만, 압축을 하는 기준 문자열 개수가 고정되어서 쉬워졌다.

3. 문제 해결

• 분석과 같이 해결했다.

4. 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(string s) {
    int answer = s.length();
    int cut = 1;
    for(;cut <= s.length() >> 1; cut++)
    {
        string before(s, 0, cut);
        string result = "";
        int count = 1;
        for(int i = cut; i < s.length(); i += cut)
        {
            string now(s, i, min({cut, (int)s.length() - i}));
            if(before == now)
                count++;
            else
            {
                if(count > 1)
                    result.append(to_string(count));
                result += before;
                before = now;
                count = 1;
            }
        }
        
        if(count > 1)
            result.append(to_string(count));
        result += before;
        answer = min(answer, (int)result.length());
    }
    return answer;
}

5. 고수의 코드를 보고 배우기

• 나는 생성자를 이용해 문자열을 잘랐고, 아래 코드는 substr을 이용해 잘랐는데, 백준같은 환경으로 속도 비교를 해보고 싶다.

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

using namespace std;

vector<string> convert(string s, int n)
{
    vector<string> v;
    for(int i = 0 ; i <s.length() ; i+=n)
    {
        v.push_back(s.substr(i,n));
    }
    return v;
}

int solution(string s) {
    int answer = 0;
    vector<string> tok;
    string before;
    int cnt = 1;
    int min = s.length();
    string str="";
    for(int j = 1 ; j <= s.length()/2 ; j++)
    {
        tok = convert(s,j);
        str = "";
        before = tok[0];
        cnt = 1;
        for(int i = 1 ; i < tok.size() ; i++)
        {
            if(tok[i] == before) cnt++;
            else
            {
                if(cnt != 1) str += to_string(cnt);
                str += before;
                before = tok[i];
                cnt = 1;
            }
        }
        if(cnt != 1)str += to_string(cnt);
        str += before;  
        min = min<str.length() ? min : str.length();
    }
    cout<<str;

    return min;
}