[C++] 프로그래머스 문자열 압축 풀이

일정한 길이로 문자열을 압축하는데 가장 짧게 압축할 수 있는 길이를 찾는 문제

인데 처음엔 어떻게 풀어야 할지 감이 안 와서 구글링해서 풀었습니다 ㅠ.ㅠ 

 

---

문제의 조건

 

1. 압축할 문자열 s가 주어짐

 

2. 같은 알파벳이 연속해 있으면 압축할 수 있는데 문자열의 처음부터 끝까지 같은 길이로만 압축해야 한다. 

aaabb 일 때

앞에는 a가 3개니까 3a로 압축하고 b는 두개니까 2b로 압축해서 3a2b로 압축하는 건 안 됨

2aa2b <- 이런 식으로 압축해야 함 

 

3. s 길이의 절반까지 탐색해서 압축이 가능한지 아닌지 확인하면 된다. 

왜냐면 최소 2번부터 압축이 가능하기 때문에 s 길이의 절반을 넘어가는데도 같은 글자가 없다면 압축이 불가능한 것이기 때문이다. 

 

4. 따라서 반복문을 통해 문자열의 처음부터 탐색하면서 압축할 수 있는 글자 길이의 수를 1부터 s 길이의 절반보다 같을 때까지 늘려보면서 가능한 모든 경우의 수를 탐색해야 한다. 

 

5. 주로 사용할 함수는 substr()과 to_string()

 

---

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

using namespace std;

int solution(string s) {
    int answer = s.length();

    for (int i = 1; s.length() / 2 >= i; i++) //s 절반까지만 탐색 
    {
        string convert, tmp;
        int count = 1;
        tmp = s.substr(0, i); //i가 증가함에 따라 비교할 문자열의 길이도 점점 늘어날 것임 
        for (int j = i; s.length() > j; j += i)
        {
            if (tmp == s.substr(j, i))
                count++; //비교대상 문자열이랑 다음 문자열이랑 같으면 카운트 증가 
            else
            {
                //같지 않으면 
                //만약 카운트가 1보다 크다면 그 전까지 같은 글자가 2개 이상 있었다는 의미다. 
                //a가 2개 있었으면 2a로 압축할 수 있다. 
                //그래서 카운트를 먼저 string으로 바꿔준 후 비교대상 문자열 tmp를 더해줘서 2a 형태로 만든다.
                if (1 < count)
                    convert += to_string(count);
                convert += tmp;
                //지금까지 비교하던 문자열이랑 더 이상 비교할 필요가 없으니까 
                //비교대상 문자열을 다음 문자열로 바꿔준 후 카운트 초기화 
                tmp = s.substr(j, i);
                count = 1;
            }
        }

        //위의 연산이 끝나면 압축된 문자열을 얻을 수 있음 
        //맨 처음 설정한 최댓값과 비교해서 최소값을 저장한다. 
        if (1 < count)
            convert += to_string(count);
        convert += tmp;
        int convertSize = convert.length();
        answer = min(answer, convertSize);
    }

    return answer;
}