[프로그래머스] 문자열 압축 c++

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

프로그래머스

 

쉬워보였지만 어려웠다.

answer를 0으로 초기화 시켜놓고 증가시켜주는 것보다

answer를 문자열 길이로 초기화 시켜놓고 일치하는 문자열이 있을 때 마다 감소시켜주는 것이 더 쉬웠다.

처음에 if 문을 if(s[i]!=if(s[j]) 문자열이 일치하지 않을때 처리를 하는 식으로 했는데 

그러면  "ababrabcabc" 같이 마지막 부분이(abcabc) 일치하는 경우에 대해서 처리가 복잡해졌다.

또한 문자열이 일치하는지 확인하는 부분을 함수로 안하고 반복문안에 넣다 보니 코드가 복잡해져서 가독성이 떨어져 나중에 헷갈렸다. 

함수로 빼니까 훨씬 간결해졌다. 일치 할때마다 unit(unit=1,2,3,4,5...)만큼 빼주고 앞에 붙는 숫자가 (ex)3ac 에서 3) 1길이 만큼 차지 하니까 1을 더해주었다. 

여기서 간과한 것이 10ac같이 10개 이상 비슷하게 되면 숫자의 길이가 1이 아니라 2가 되기 때문에  ans를 하나 더 증가시켜주어야 한다. 

테스트 케이스에서는 이렇게만 해도 정답이 나오지만 문자열의 길이가 1000이하이기 때문에 100a,와10a도 나올 수 있기 때문에 처리를 해줬다.

총 3중 반복문이다. 첫 번째는 비교할 첫번째 문자열의 위치를 가리키는 i ,두 번째는 비교할 두번째 문자열의 위치를 가리키는 j, 3번째는 문자열 안에서의 인덱스를 가리키는 k.

k는 0부터 unit 사이의 값이다.

처음에 변수의 역할을 정하고 일반적인 상황을 생각해서 풀어야 했는데 무작정 작성하면서 생각하니까 코드가 엄청 복잡해졌었다.( unit이 1인경우와 2인경우만 생각)(answer를 줄일지 늘릴지에 대해서 생각 x)(문자열 마지막에 일치하는 문자가 있으면 어떻게 할지 생각x)

* if문에서 true일때와 false ,어느 때를 처리하는 것이 더 좋을지

*케이스 몇개만 가지고 풀지 말고 일반적인 상황을 가정하고 풀기

 

#include <string>
#include <vector>
#include<iostream>
using namespace std;
string ss;
//string ss를 i위치와 j 위치에서 l 길이만큼 비교
bool aa(int i,int j,int l)
{
    for(int k=0;k<l;k++)
    {
        if(ss[i+k]!=ss[j+k])
            return false;
    }
    return true;
}
int solution(string s) {
    int answer = s.length();
   
    ss=s;
    int size=s.length();
    int point=0;
    int unit=1;
    bool check=false;
    int cnt=0;
    while(unit<=(size/2)){
         int ans = s.length();
        for(int i=0;i<=size-unit*2;i=point)
        {
            cnt=0;
            for(int j=i+unit;j<size;j+=unit)
            {
                point=j;
                
                if(aa(i,j,unit))//i,j,s
                {
                    ans-=unit;
                    check=true;
                    cnt++;
                }
                else
                {
                    break;
                }
                
                
            }
            if(check)//압축된적이 있으면
            {
                ans++;
               if(cnt>8)//10번이상 압축되면 
                    ans++;
               if(cnt>98)
               	    ans++;
               if(cnt>998)
                    ans++;
                check=false;
            }
        }
        if(ans<answer)
        {
           
            answer=ans;
        }
        unit++;
    }

    return answer;
}