프로그래머스 - 문자열 압축 - C++

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

프로그래머스

 

#include <string>
#include <vector>

using namespace std;

int solution(string s) {
    int answer = 1001;
    
    if(s.length()==1)
        return 1;
    
    for(int i=1;i<=s.length()/2;i++)
    {
        string temp = "";
        int j;
        for(j=0;j<=s.length()-i;j+=i)
        {
            int cnt=1;
            while(s.substr(j,i)==s.substr(j+i,i))
            {
                cnt++; j+=i;
            }
            if(cnt>1)
            {
                temp += to_string(cnt) + s.substr(j-i,i);
            }
            else
                temp+=s.substr(j,i);
        }
        if(j>s.length()-i)
            temp+=s.substr(j);
        if(temp.length()<answer)
            answer=temp.length();
    }
    
    return answer;
}

이 문제는 주어진 방법대로 문자열 압축을 했을 때 가장 짧게 압축됐을 때의 길이를 리턴하는 문제이다. 

단위가 1일 때, 문자열의 처음부터 1로 자르고 연속되는 패턴이 있다면 (연속되는 수)(패턴) 으로 압축을 한다. 

단위가 2일 때도 마찬가지이다. 

 

for문을 통해 단위를 기준잡고 그에 따라 substr을 while로 돌려서 압축길이를 저장하는 방식으로 접근한다.

 

먼저 길이가 1이면 굳이 계산할 필요없다. 

 

for(int i=1;i<=s.length()/2;i++)

i for문은 단위인데 길이의 절반까지만 계산한다. 절반이 넘어가면 어차피 압축이 안되기 때문이다. 

 

for(j=0;j<=s.length()-i;j+=i)

다음은 i for문안에 있는 j for문이다. 

j는 인덱스로 길이-i 까지 동작한다. 

 

int cnt=1;
while(s.substr(j,i)==s.substr(j+i,i))
{
     cnt++; j+=i;
}

j for문 안에 while문이다. 

인덱스 j를 기준으로 단위만큼 자른 문자열과 그 다음 단위만큼 자른 문자열이 같은지 확인한다. 

다음문자열과 다를 때까지 while문을 돌며 카운트한다. 이 때, j값도 같이 증가시킨다. 

while이 종료되면 자연스레 그 다음부터 다시 패턴이 있는지 비교하게 된다. 

 

if(cnt>1)
            {
                temp += to_string(cnt) + s.substr(j-i,i);
            }
            else
                temp+=s.substr(j,i);

while 문이 종료되고 cnt가 만약 1이상이라면 패턴이 한번이라도 있었다는 것이고 j도 한번이상증가했다는 뜻이다.

따라서 aa 를 2a 식으로 바꾸는 것이다.

 

cnt가 1이라면 그대로 temp에 더한다. 

 

if(j>s.length()-i)
            temp+=s.substr(j);
        if(temp.length()<answer)
            answer=temp.length();

j for문이 종료되면 if문으로 비교하는데 길이가 8인 문자열에서 단위 3으로 계산할 때 뒤에 2는 j for문 조건에 걸려서 계산이 안되기 때문에 나머지를 뒤에 붙이는 작업이다. 

 

단위 i로 압축했을 때 가장 짧은 길이인지를 확인하고 answer에 교체한다.