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

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

코딩테스트 연습 - 문자열 압축

#include <string>
#include <vector>
#include <cmath>

using namespace std;

class bucket{
    public:
    int index;
    string pstr;
    int cnt;
    bucket(int index, string pstr, int cnt){
        this->index=index;
        this->pstr=pstr;
        this->cnt=cnt;
    }
};

int solution(string s) {
    int len=s.length();
    int answer = len;
    for (int i=1; i<len; i++){
        int ans=0;
        bucket b=bucket(i, s.substr(0,i), 1); 
        ans+=b.pstr.length();
        while (b.index<len){
            if (b.index+i>len){
                ans+=(len-b.index);
                break;
            }
            int start=b.index;
            string temp="";
            for (int j=start; j<start+i; j++){
                temp+=s[j];
            }
            if (temp.compare(b.pstr)==0){       //비교군과 같을 때
                b.cnt+=1;
                if (b.cnt==2){      //같은거 2개 나올때
                    ans+=1;
                }
                else if (int(log10(b.cnt-1) + 1) < int(log10(b.cnt)+1)){    //자릿수 증가
                    ans+=1;
                }
            }
            else{           //비교군과 다를 때
                b.cnt=1;
                b.pstr=temp;
                ans+=b.pstr.length();
            }
            b.index+=i;
        }
        answer=(ans<answer) ? ans: answer;
    }
    return answer;
}

 

카카오 기출. Level 2.

구현 능력+문자열 다루기. 헤맸던 문제. (ㅜㅜ)

 

시간복잡도는 O(N^2) 로 단위 별로 쪼개서 가장 작은 걸 선택해주면 된다.

그런데 여기서 중요한건 N/2 조각까지만 쪼개도 된다는 것이다.

그 이상 하면 어차피 의미가 없다. 그 이상 하면 기존 압축되지 않은 문자열 길이와 똑같아지므로 의미가 없다.

(이 부분을 문제 풀기전에 머릿속으로 시뮬레이션 해봤어야 하는데 문제푸느라 급급해서 못했다, 이 경우도 O(N^2) 로 나와서 시간 복잡도에 큰 영향은 없었지만..)

 

나는 bucket 이라는 class를 만들어서 비교대상인 문자열, 그 문자열이 반복된 횟수, 탐색을 할 시작 인덱스 값을 저장했다.

그런데 이렇게 할 필요 없이 for문으로 간단히 돌려주고, cnt 변수만 있으면 된다 (참고: https://yjyoon-dev.github.io/kakao/2020/11/05/kakao-strzip/ ) .

 

나는 같은거 나올때 cnt를 세주고(이때 자릿수를 계산해서 자릿수가 바뀌면 ans+1 해주는걸로.. 매우 복잡해보인다), 비교군과 다른 새로운거 나올땐 그 문자열의 길이를 세줘서 ans에 집어넣었다. 로직이 깔끔하진 않다.

 

이 분의 코드를 보니 비교군 temp 문자열을 만들고, 다음 문자열들을 정해진 단위만큼 탐색한 뒤,

동일한 것이 나오면 cnt++ 해주고, 동일한 것이 나오지 않으면 cnt가 2 이상(즉 압축될 수 있다는 의미) 나오면 

cnt 를 스트링 변환해줘서 convert 스트링에 집어넣는다. 이후 비교군 temp 문자열도 convert 스트링에 넣어주고, 

이제 새로운 비교군을 temp에 집어넣어주고 cnt는 1으로 설정한다. 이렇게 하면 복잡했던 걸 한번에 해결할 수 있다..

비교할때 범위를 벗어난것이 나오면, 기존 cnt가 2이상이면 cnt 값을 convert 문자열에 넣어주고, 비교군도 convert 문자열에 넣어준다.