문자열 압축(42분)

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

문제 이해 5분 구현 아이디어 5분 구현 32분

1. 문자열의 길이가 길지 않아 경우를 전부 탐색 했는데 이렇게 풀고 싶지는 않았다. DFS를 이용해서 풀 수 있는 문제라고 하여 다른 사람들의 풀이를 살펴 볼 예정. 일단 나의 풀이.

#include <string>
#include <vector>

using namespace std;

int solution(string s) {
    int answer = 0;
    int mini = 2147000000;
        
    // i는 자를 단위
    for(int i = 1; i <= s.length(); ++i)
    {
        int cnt = 1;
        string press, now, comp;
        
        // 앞에서 부터 자른 문자열
        for(int j = 0; j < i; ++j)
            now += s[j];
        
        for(int j = i; j < s.length(); j += i)
        {
        	// 비교할 문자열을 만들어 준다.
            comp.clear();
            for(int k = j; k < (j + i) && s[k] != '\0'; ++k) comp += s[k];
            
            if(now == comp)
            {
                cnt++;
                continue;
            }
            else
            {
                if(cnt == 1) press += now;
                else press += (to_string(cnt) + now);
                
                now = comp;
                cnt = 1;
            }
        }
        
        if(cnt == 1) press += now;
        else press += (to_string(cnt) + now);
        
        if(press.length() < mini)  mini = press.length();
    }
    
    answer = mini;
    
    return answer;
}

---

개인적인 감상.
구현을 어떻게 할지 생각하는데 길게 걸리는 문제도 있기 때문에 이렇게 좋지 않은 구현법이라도 아이디어가 빨리 떠올랐을 때는 구현 속도가 빨라야하는데 나는 아직 너무 부족하다.
완전탐색으로 경우를 전부 검색하는 로직일 뿐인데 구현에 32분이 걸렸고 중간에 막혀 비주얼 스튜디오로 디버깅까지 해버렸다... 분발해야지.

---

구글에서 다른 글들을 참고하여 좋은 아이디어를 발견했다.
전체 문자열의 절반 초과가 기준점이면 아예 압축이 안되기 때문에 검사해 줄 필요가 없다는 사실이었다. 확실히 시간이 줄어든다.

단순히 
	// i는 자를 단위
    for(int i = 1; i <= s.length(); ++i) 이 부분을
    for(int i = 1; i <= s.length() / 2 + 1; ++i) 이렇게 바꿔주면 된다.

---

다른 사람들의 풀이 보기에서 좋은 풀이를 봤다. vector 컨테이너에 미리 해당 단위에 맞게 자른 문자열들을 넣고 비교해주는 풀이었다. 해당 풀이를 공부해 다시 풀어봤더니 채점 시간이 절반이나 줄었다.

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

using namespace std;

// s는 자를 원본 문자열, n은 자를 단위
vector<string> convert(string s, int n)
{
    vector<string> res;
    
    // n의 단위만큼 이동하며 잘라야 한다.
    for(int i = 0; i < s.length(); i += n)
    {
        // s.substr(i부터, n개 만큼 자른다.);
        res.push_back(s.substr(i, n));
    }
    
    return res;
}

int solution(string s) {
    int answer = 0;
    
    string before = "";
    string str = "";
    vector<string> comp;
    int cnt = 1;
    int mini = s.length();
    
    for(int i = 1; i <= s.length() / 2; ++i)
    {
        // i 단위로 자른 문자열들을 리턴 받는다.
        comp = convert(s, i);
        
        // 맨 처음 문자열을 before에 넣어준다.
        before = comp[0];
        
        // 이 둘의 초기화를 잊지 말자.
        cnt = 1;
        str = "";
        
        for(int j = 1; j < comp.size(); ++j)
        {
            // 같으면 넘어간다.
            if(comp[j] == before) cnt++;
            
            // 다를 때 cnt가 1보다 크다면 cnt와 함께 문자열을 추가한다.
            else
            {
                if(cnt != 1) str += to_string(cnt);
                str += before;
                
                // before와 cnt를 갱신한다.
                before = comp[j];
                cnt = 1;
            }
        }
        
        // 마지막 남은 문자열을 잊지말자.
        if(cnt != 1) str += to_string(cnt);
        str += before;
                
        mini = mini < str.length() ? mini : str.length();
    }
    
    return answer = mini;
}