[ 프로그래머스 문자열 압축 (Lv2) ] (C++)

프로그래머스의 문자열압축(Lv2) 문제이다.

[ 문제풀이 ]

먼저, 문제를 풀기 전 주의해야 할 사항과 진행과정을 순차적으로 알아보자.

#1 압축할 문자의 갯수는 동일하다.

본인이 가장 처음에 놓쳤던 것은, 압축할 문자의 갯수는 동일하다는 것이다.

예를 들어서 예시로 주어진 입력 케이스 중에서 4번 케이스를 보면, "abcabcabcabcdededededede" 이라는 문자열이 있다.

이 문자열은 "4abc6de" 로 압축이 되지 않는 다는 것이다.

왜냐하면, 위와 같이 압축을 할 경우, "abc"라는 문자열은 3개의 단위로 압축을 한 것이고, "de"라는 문자열은 2개의 단위로 압축을 한 것이기 때문에 올바르게 압축한 경우가 아니라는 것이다.

즉, 전체문자열을 압축할 때, 압축할 문자의 갯수는 동일하게 설정을 해야 한다는 것이다.

#2 압축할 문자의 갯수 설정

본격적인 압축을 하기에 앞서, 주어진 문자열에서 최대 몇 개 까지 압축이 가능한지 보자.

예를 들어서 "abab"라는 문자열이 주어졌다고 가정해보자. 이 문자열은, 문자를 1개씩 압축을 하는 것도 가능하고, 2개 단위로 압축을 하는 것도 가능하다. 3개는 가능할까 ?? 3개와 4개는 불가능하다.

그럼, "aaaa"라는 문자열을 생각해보자. 이 문자열은, 문자를 1개 단위로 압축해서 "4a"라는 문자열로 만들 수도 있고, 2개 단위로 압축해서, "2aa"도 가능하다. 3개는 가능할까 ?? 3개는 불가능하다.

우리는 여기서, 압축할 수 있는 문자의 최대갯수를 알 수 있다.

바로, 주어진 문자열의 길이를 Len 이라고 가정했을 때, 압축할 수 있는 문자의 최대갯수는 Len / 2개 라는 것이다.

그 이상의 갯수로 문자를 압축하는 것은 불가능하다.

#3 압축하기

본인은 1개 단위부터 ~ Len / 2개 단위까지 압축하는 모든 경우를 진행해 보았다.

그럼 지금부터, 주어진 문자열을 K개 단위로 압축하는 경우, 그 과정을 알아보자.

먼저 과정을 크게 말하자면, 우리는 모든 경우를 탐색할 때, 만들어 지는 문자열을 새로 저장해 줄 것이고, 이 새로 만들어진

문자열의 길이와 기존의 답을 비교하면서 갱신해줄 것이다.

다음 예시를 가지고 그 과정을 진행하겠다. [ "abab" ] 와 [ "abcd" ] 라는 문자열을, 2개 단위로 압축하는 경우이다.

1. 가장 먼저, 0번 Index부터 2개의 단어로 이루어진 문자열을 저장한다. (저장한 string명 : Temp)

   동시에, 현재 까지 'Temp'가 몇 번 나왔는지 또한 기록한다.

   그럼, 현재까지 Temp는 1번 나온 것이다.

   [ "abab" ] 와 [ "abcd" ] 2가지 경우 모두, Temp = "ab"가 되고, "ab"가 현재까지 나온 횟수는 1회가 된다.

2. 이 후, 2번 Index부터 2개씩 건너뛰면서 문자열을 확인해본다.

2-1) 확인한 문자열이 Temp와 같다면, Temp가 나온 횟수를 ++ 시켜준다. 그리고 탐색을 계속한다.

     [ "abab" ] 의 경우 , 그 다음에 나온 문자열이 "ab"로,  Temp와 같기 때문에, 현재까지 "ab"가 나온 횟수는 2회가 나온다.

2-2) 하지만, Temp와 같지 않다면, Temp를 새로운 문자열에 저장을 해준다.

     이 떄, 새로운 문자열을 string Result 라고 가정해보자.

     [ "abcd" ] 같은 경우, 현재 Temp = "ab"인데, 그 다음 2개의 문자열을 확인해보니 ,"cd" 로 Temp와 같지가 않다.

     따라서, 이 경우에는 Result 만들어진 새로운 문자열을 저장할 변수에 Temp를 저장해준다.

     즉, Result = "ab" 가 된다. 그리고 Temp의 값을 "cd"로 변경해준다. Temp가 현재까지 나온 횟수 또한 1회로 다시

     초기화를 시켜준다.

3. 위의 과정을 반복하면서, Result의 길이와 기존의 문자열의 길이를 비교하면서 가장 짧은 문자열의 길이로 정답을 갱신해준

   다.

[ 소스코드 ]

#include <string>
#include <vector>
 
using namespace std;
 
int Min(int A, int B) { return A < B ? A : B; }
 
int solution(string s) 
{
    int answer = s.length();
    for (int Len = 1; Len <= s.length() / 2; Len++)
    {
        /* 압축할 단위는 1개부터 , 문자열의 길이까지 압축이 가능하므로 모든 경우 탐색. */
        /* Result = 압축해서 나온 새로운 문자열을 저장할 변수 */
        /* Temp = 현재 압축해서 비교를 하기 위한 문자열 */
        /* Cnt = Temp가 현재까지 나온 횟수. */
        string Result = "";
        string Temp = s.substr(0, Len);
        int Cnt = 1;
        int i;
        for (i = Len; i <= s.length(); i = i + Len)
        {
            /* Temp와 그 다음 자른 문자열이 동일하면, Cnt++ */
            /* 그게 아니라면 , Result에 Temp를 옮기고, Temp에 새로운 문자열을 저장.*/
            if (Temp == s.substr(i, Len)) Cnt++;
            else
            {
                if (Cnt == 1) Result += Temp;
                else
                {
                    Result += to_string(Cnt);
                    Result += Temp;
                }
                
                Temp = s.substr(i, Len);
                Cnt = 1;
            }            
        }
 
        /* 예외적인 경우. 문자열의 길이를 넘어서서, 마지막 몇 개의 문자가 짤리는 경우가 발생. */
        /* 이 경우에는, 문자열이 짤리지 않도록 하기 위해서, 한번 더 진행. */
        if (i > s.length())
        {
            if (Cnt == 1) Result += Temp;
            else
            {
                Result += to_string(Cnt);
                Result += Temp;
            }
        }
        answer = Min(answer, Result.length());
    }
    return answer;
}