문자열 압축

문제 설명

 

제한사항

• s의 길이는 1 이상 1,000 이하입니다.
• s는 알파벳 소문자로만 이루어져 있습니다.

입출력 예

s                                                                                                                                                                               result

"aabbaccc"	7
"ababcdcdababcdcd"	9
"abcabcdede"	8
"abcabcabcabcdededededede"	14
"xababcdcdababcdcd"	17

 

입출력 예에 대한 설명

입출력 예 #1

문자열을 1개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #2

문자열을 8개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #3

문자열을 3개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #4

문자열을 2개 단위로 자르면 "abcabcabcabc6de" 가 됩니다.
문자열을 3개 단위로 자르면 "4abcdededededede" 가 됩니다.
문자열을 4개 단위로 자르면 "abcabcabcabc3dede" 가 됩니다.
문자열을 6개 단위로 자를 경우 "2abcabc2dedede"가 되며, 이때의 길이가 14로 가장 짧습니다.

입출력 예 #5

문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다.
따라서 주어진 문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능 합니다.
이 경우 어떻게 문자열을 잘라도 압축되지 않으므로 가장 짧은 길이는 17이 됩니다.

 

 

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


using namespace std;

int solution(string s) {
    int answer = s.size();
    int sSize = s.size();
    int limit = s.size()/2;
    
    for(int div =1; div<= limit; div++)
    {
        string newS=""; //사이즈 측정할 문자열
        int cnt=1;
        string comS=s.substr(0,div); // 비교할 문자열
        for(int i=div; i<=sSize; i+=div)
        {
            if( comS == s.substr(i,div)) //중복되는 문자열이 있는 경우
            {
                cnt++;
            }
            else //중복되지 않는 경우 ( 끝부분에 없는 경우에서 걸릴 수 있음)
            {
                if(cnt == 1)
                {
                    newS += comS;
                }
                else
                {
                    newS += to_string(cnt)+comS;
                }
                    comS = s.substr(i,div); cnt=1;
            }
            
        }
        
        if(sSize%div != 0) // 나누는 숫자의 단위가 숫자의 길이로 나누어떨어지지 않을 경우
        {
            newS += s.substr((sSize/div)*div);
        }
        answer = min(answer, (int)newS.size());
    }
    return answer;
}

 

 

=> 1,2,3,.... s의 길이의 반까지로 나눠보는 과정을 진행해야 합니다. 

=> 과정을 진행하며, 나누는 숫자가 s의 길이로 딱 나누어떨어지지 않을 때는 나머지 부분을 붙여야하는 점을 염두에 둬야합니다. 

=> algorithm 헤더에 있는 min 함수의 경우 parameter를 int형만 받습니다. string의 size()함수의 경우, double형을 반환하기 때문에 형변환을 하며 함수를 적용해야 합니다. 

length() 메소드와 size() 메소드

length() 메소드는 문자열의 길이를 반환하는 메소드입니다.
size() 메소드도 length() 메소드와 언제나 같은 값을 반환하지만, 그 의미는 약간 다릅니다.
 
length() 메소드는 문자열의 길이를 나타내지만, size() 메소드는 해당 string 객체가 메모리에서 실제 사용하고 있는 크기를 나타냅니다.

=> 위와 같이 string class에 있는 length() 함수와 size() 함수는  각각 문자열의 길이와, 객체가 메모리에서 사용하고 있는 크기를 나타냅니다.